oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

bombing Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

bombing.html

Problem Description

The city of Catville has come under attack! The structure of Catville can be described as a series of N intersections, with E roads, and each road i connecting two intersections Si and Ti.

A total of B bombs have been dropped on Catville, and the ith bomb has been dropped at intersection Xi with a power of Yi. The power of a bomb decides the extent of damage it can cause. A power 1 bomb will only damage the intersection it lands on, a power 2 bomb will damage the intersection it lands on as well as its neighbours, and so on. In general, a power x bomb will damage all intersections that are reachable from Xi with less than x roads.

After the attack, the mayor of Catville wants to know, how many intersections of Catville have been damaged.

Input

The first line of input will contain three integers, N, E and B.

The next E lines of input will contain two integers each, Si and Ti.

The next B lines of input will contain two integers each, Xi and Yi.

Output

The output should contain one line with one integer, the number of damaged intersections.

Limits

For all subtasks: 1 ≤ B ≤ N ≤ 500 000, 1 ≤ E ≤ 1 000 000, 1 ≤ Si, Ti, Xi ≤ N, 1 ≤ Yi < N. No two bombs will fall on the same spot.

Subtask 1 (3%): Yi = 1.

Subtask 2 (9%): 1 ≤ N ≤ 1 000, E = N - 1, Si = i, Ti = i + 1.

Subtask 3 (15%): 1 ≤ N ≤ 1 000, 1 ≤ E ≤ 2 000.

Subtask 4 (18%): B = 1.

Subtask 5 (11%): E = N - 1, Si = i, Ti = i + 1.

Subtask 6 (10%): E = N, Si = i, Ti = i % N + 1.

Subtask 7 (13%): 1 ≤ N ≤ 100 000, 1 ≤ E ≤ 200 000.

Subtask 8 (21%): No additional constraints.

Subtask 9 (0%): Sample Testcases.

Sample Input 1

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

Sample Output 1

4

Sample Input 2

5 4 2
1 2
2 3
3 4
4 5
3 1
4 3

Sample Output 2

4

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
13201.5s256MBMinimum
29211.5s256MBMinimum
315421.5s256MBMinimum
418201.5s256MBMinimum
511411.5s256MBMinimum
610201.5s256MBMinimum
713621.5s256MBMinimum
8211621.5s256MBMinimum
9021.5s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o bombing -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.