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 |
19 ms |
3144 KB |
Output is correct |
| 2 |
Correct |
18 ms |
3100 KB |
Output is correct |
| 3 |
Correct |
26 ms |
3308 KB |
Output is correct |
| 4 |
Correct |
39 ms |
3364 KB |
Output is correct |
| 5 |
Correct |
85 ms |
3664 KB |
Output is correct |
| 6 |
Correct |
122 ms |
5800 KB |
Output is correct |
| 7 |
Correct |
303 ms |
4744 KB |
Output is correct |
| 8 |
Correct |
349 ms |
5172 KB |
Output is correct |
| 9 |
Runtime error |
57 ms |
7196 KB |
Execution failed because the return code was nonzero |
| 10 |
Correct |
1927 ms |
9112 KB |
Output is correct |
| 11 |
Correct |
5141 ms |
9460 KB |
Output is correct |
| 12 |
Runtime error |
125 ms |
11968 KB |
Execution failed because the return code was nonzero |
| 13 |
Execution timed out |
8100 ms |
11552 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8009 ms |
12368 KB |
Time limit exceeded |
| 15 |
Runtime error |
168 ms |
14852 KB |
Execution failed because the return code was nonzero |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1800 ms |
24928 KB |
Execution failed because the return code was nonzero |
| 2 |
Runtime error |
1641 ms |
25716 KB |
Execution failed because the return code was nonzero |
| 3 |
Runtime error |
1577 ms |
29148 KB |
Execution failed because the return code was nonzero |
| 4 |
Runtime error |
349 ms |
40664 KB |
Execution failed because the return code was nonzero |
| 5 |
Runtime error |
434 ms |
50500 KB |
Execution failed because the return code was nonzero |
| 6 |
Runtime error |
4920 ms |
85844 KB |
Execution failed because the return code was nonzero |
| 7 |
Runtime error |
2445 ms |
103896 KB |
Execution failed because the return code was nonzero |
| 8 |
Runtime error |
7985 ms |
131076 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
895 ms |
131076 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
719 ms |
131076 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
730 ms |
131076 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
812 ms |
131076 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
785 ms |
131076 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
707 ms |
131076 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
725 ms |
131076 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
720 ms |
131076 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
717 ms |
131076 KB |
Execution killed with signal 9 |
