import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
sys.setrecursionlimit(5 * 10**6)
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 |
48 ms |
18988 KB |
Output is correct |
| 2 |
Correct |
54 ms |
19188 KB |
Output is correct |
| 3 |
Correct |
78 ms |
19616 KB |
Output is correct |
| 4 |
Correct |
117 ms |
21896 KB |
Output is correct |
| 5 |
Correct |
167 ms |
24596 KB |
Output is correct |
| 6 |
Correct |
224 ms |
27280 KB |
Output is correct |
| 7 |
Correct |
280 ms |
26364 KB |
Output is correct |
| 8 |
Correct |
255 ms |
29060 KB |
Output is correct |
| 9 |
Correct |
342 ms |
32684 KB |
Output is correct |
| 10 |
Correct |
495 ms |
33916 KB |
Output is correct |
| 11 |
Correct |
724 ms |
30140 KB |
Output is correct |
| 12 |
Correct |
742 ms |
38456 KB |
Output is correct |
| 13 |
Correct |
1091 ms |
34316 KB |
Output is correct |
| 14 |
Correct |
1764 ms |
35672 KB |
Output is correct |
| 15 |
Correct |
2181 ms |
80352 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
505 ms |
56228 KB |
Execution failed because the return code was nonzero |
| 2 |
Runtime error |
539 ms |
56636 KB |
Execution failed because the return code was nonzero |
| 3 |
Runtime error |
600 ms |
91464 KB |
Execution failed because the return code was nonzero |
| 4 |
Correct |
1572 ms |
67040 KB |
Output is correct |
| 5 |
Correct |
1796 ms |
98464 KB |
Output is correct |
| 6 |
Incorrect |
1580 ms |
114888 KB |
Output isn't correct |
| 7 |
Runtime error |
508 ms |
131076 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
510 ms |
131076 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
162 ms |
131076 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
206 ms |
131076 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
144 ms |
131076 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
158 ms |
131076 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
177 ms |
131076 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
154 ms |
131076 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
144 ms |
131076 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
145 ms |
131076 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
151 ms |
131076 KB |
Execution killed with signal 9 |
