def add(x, v):
global n, bit
x += 1
while x <= n:
bit[x] += v
x += x & (-x)
def qry(x):
global bit
ret = 0
x += 1
while x > 0:
ret += bit[x]
x -= x & (-x)
return ret
def dfs(c):
global p, l, r, g
r[c] = l[c]
for i in g[c]:
if i != p[c]:
l[i] = r[c] + 1
r[c] = dfs(i)
return r[c]
def main():
global n
n, k, q = map(int, input().split())
m = 447 #sqrt const
t = 0
global p, l, r, bit, g
a = [0] * n
p = [0] * n
dp = [0] * n
l = [0] * n
r = [0] * n
bit = [0] * (n + 1)
b = [0] * k
f1 = [[0 for j in range(k)] for i in range(m)]
f2 = [[0 for j in range(k)] for i in range(m)]
g = [[] for i in range(n)]
w = [[] for i in range(k)]
for i in range(n):
if i:
p[i], a[i] = map(int, input().split())
p[i] -= 1
g[p[i]].append(i)
else:
p[i] = -1
a[i] = int(input())
a[i] -= 1
w[a[i]].append(i)
for i in range(k):
if len(w[i]) > m:
for j in range(n):
if a[j] == i:
dp[j] = 1
if p[j] != -1:
dp[j] += dp[p[j]]
f1[t][a[j]] += dp[j]
dp = [0] * (n + 1)
for j in reversed(range(n)):
if a[j] == i:
dp[j] += 1
f2[t][a[j]] += dp[j]
if p[j] != -1:
dp[p[j]] += dp[j]
b[i] = t
t += 1
else:
b[i] = -1
dfs(0)
for qq in range(q):
x, y = map(int, input().split())
x -= 1
y -= 1
if b[x] != -1:
print(f1[b[x]][y])
elif b[y] != -1:
print(f2[b[y]][x])
else:
ret = 0
for i in w[y]:
add(l[i], 1)
for i in w[x]:
ret += qry(r[i]) - qry(l[i] - 1)
for i in w[y]:
add(l[i], -1)
print(ret)
main()
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
59 ms |
18968 KB |
Output is correct |
| 2 |
Correct |
51 ms |
18972 KB |
Output is correct |
| 3 |
Correct |
78 ms |
19356 KB |
Output is correct |
| 4 |
Correct |
119 ms |
21560 KB |
Output is correct |
| 5 |
Correct |
156 ms |
24084 KB |
Output is correct |
| 6 |
Correct |
280 ms |
26832 KB |
Output is correct |
| 7 |
Correct |
244 ms |
26860 KB |
Output is correct |
| 8 |
Correct |
319 ms |
28900 KB |
Output is correct |
| 9 |
Runtime error |
189 ms |
28204 KB |
Execution failed because the return code was nonzero |
| 10 |
Correct |
479 ms |
33816 KB |
Output is correct |
| 11 |
Correct |
672 ms |
30636 KB |
Output is correct |
| 12 |
Runtime error |
232 ms |
32460 KB |
Execution failed because the return code was nonzero |
| 13 |
Correct |
993 ms |
34228 KB |
Output is correct |
| 14 |
Correct |
1719 ms |
35964 KB |
Output is correct |
| 15 |
Runtime error |
275 ms |
33088 KB |
Execution failed because the return code was nonzero |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
451 ms |
43288 KB |
Execution failed because the return code was nonzero |
| 2 |
Runtime error |
507 ms |
56756 KB |
Execution failed because the return code was nonzero |
| 3 |
Runtime error |
407 ms |
49736 KB |
Execution failed because the return code was nonzero |
| 4 |
Correct |
1698 ms |
65876 KB |
Output is correct |
| 5 |
Runtime error |
310 ms |
68152 KB |
Execution failed because the return code was nonzero |
| 6 |
Incorrect |
1603 ms |
116904 KB |
Output isn't correct |
| 7 |
Runtime error |
444 ms |
131076 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
488 ms |
131076 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
148 ms |
131076 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
231 ms |
131076 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
142 ms |
131076 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
175 ms |
131076 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
145 ms |
131076 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
143 ms |
131076 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
145 ms |
131076 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
139 ms |
131076 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
149 ms |
131076 KB |
Execution killed with signal 9 |
