5301: WeChat Walk
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：3
解决：1
题目描述
When WeChat first introduced the function of "counting steps",people began to compete with each other.
The function of "counting steps" involves two parts:
- Count the steps he/she walks today.
- Show the one who walks most today in he/she's friend list, we may call the one a "walking champion".
In each minute, he/she may walk more, so the "walking champion" in he/she's friend list changes dynamically.
In this problem, There are n people in total, numbered from 1 to n. Friendships are described as a undirected graph with n{n}n vertices and m edges.
We divide a day into q time units. In each time unit, only one person walks several steps. One becomes "walking champion" in he/she's friend list, if and only if he/she walks at least 1 step and the number of his walking steps is strictly greater than anyone else's in he/she's friend list.
You are given the graph, who walks and how many steps he/she walks in each time unit.
For each person, you are asked to calculate the total number of time units that he/she becomes a "walking champion" in he/she's friend list.
To be more specific, if one became a champion after lth time unit, and ended after rth time unit (if he/she keeps a championship until the end, then r=q, then we say he/she becomes a champion for r−l time unit(s).
For each person, you are asked to calculate the total number of time units that he/she becomes a "walking champion" in he/she's friend list.
To be more specific, if one became a champion after lth time unit, and ended after rth time unit (if he/she keeps a championship until the end, then r=q, then we say he/she becomes a champion for r−l time unit(s).
输入
Input consists of m+q+1 lines.
The firsts line contains n,m,q{n,m,q}n,m,q — the number of people, the number of friendships, the number of time units.
Then m{m}m lines ,each line contains two integer xi,yi,denoting the ith friendship.
Then q lines, each line contains two integer uj,wj, denoting that the ujth person walks wj steps during jth time unit.
输出
Output n lines, ith line contains the total number of time units that ith person becomes a "walking champion" in he/she's friend list.
样例输入 复制
10 10 10
5 7
3 7
7 9
6 9
1 5
1 4
5 6
7 8
4 6
3 6
3 201
5 6266
2 2593
1 3241
5 1028
2 6040
4 1025
1 5563
7 3741
6 6129样例输出 复制
2
7
8
0
6
0
0
0
0
0提示
n,m,q≤200000,1≤xi,yi,uj≤n，1≤wj≤10000.
It's guaranteed that xi≠yi, any (xi,yi)(x_i,y_i)(xi,yi) does not appear twice in the graph and at any time nobody walks more than 10000 steps.