DMOPC '15 Contest 6 P6 - Graf Zeppelin - Olympiads Online Judge

DMOPC '15 Contest 6 P6 - Graf Zeppelin

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.4s

Memory limit: 256M

Author:

FatalEagle

Problem type

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

Input Specification

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

Output Specification

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

Sample Input 1

Copy

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

Comments

0

sre0x2a commented 61 days ago

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?