DMOPC '15 Contest 6 P6 - Graf Zeppelin

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 1.4s
Memory limit: 256M
Author:
FatalEagle
Problem type

Graf has a graph, a graph with N vertices and M bidirectional edges. In this graph, Graf wonders: for each vertex how many vertices are within distance K of it?

Input Specification

The first line will have space-separated N (1 \le N \le 1\,500), M (1 \le M \le \frac{N \times (N-1)}{2}), and K (1 \le K \le 5).
The next M lines will describe the edges: there is an edge between every pair of integers on the next M lines. Edges will not be repeated in the input.
10\% of the test data will additionally have N \le 200.

Output Specification

Output N lines, the answer for vertex number i on line i.

Sample Input 1

6 7 1
1 2
2 3
1 4
2 5
4 6
3 4
2 6

Sample Output 1

3
5
3
4
2
3

Sample Input 2

4 6 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4
4
4
4

Comments


  • 0
    sre0x2a  commented on Jan. 24, 2025, 12:14 p.m.

    I assumed this would essentially be an all pairs shortest path preprocessing step but it appears that is too slow. Any hints on the type of algorithm to look into for this? A tree reroot with a general graph exploration to establish search tree depth first seemed like a decent idea but I can't see how you can reroot with a graph vs a tree.


  • 2
    minecraftyugi  commented on March 7, 2016, 2:20 p.m.

    Is this question solvable in python?