← CSES Better

A Graph Problem

USACO · 2023 · December · platinum-2

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

graph-algorithms · trees · data-structures

The organizer’s problem statement is available at the official source link.

sample trace

A Graph Problem: graph algorithms walkthrough

A Graph Problem: use the linked editorial?s graph algorithms, trees idea on the published sample, then verify the displayed output.

Published input3 2 1 2 2 3 5 6 1 2 3 4 2 4 2 3 2 5 1 5 15 14 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15modelAlgorithm ideaRepresent the task?s objects and connections as a graph, then use the editorial?s traversal or path method to obtain the requested property.task resultExpected output12 12 21 1325 1325 2315 2315 5132 678925929 678925929 678862929 678787329 678709839 678632097 178554320 218476543 321398766 431520989 542453212 653475435 764507558 875540761 986574081
  1. 1

    Model

    Make one vertex per task object and add an edge for each permitted relationship.
  2. 2

    Process

    Traverse or relax the graph according to the task?s path or reachability rule.
  3. 3

    Read

    Use the reached set or path result to produce the requested output.
  4. 4

    Verify the sample

    Use the published sample output to check the result of this idea on the displayed input.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.