import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
sys.setrecursionlimit(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 |
18 ms |
3252 KB |
Output is correct |
| 2 |
Correct |
17 ms |
3144 KB |
Output is correct |
| 3 |
Correct |
25 ms |
3264 KB |
Output is correct |
| 4 |
Correct |
41 ms |
3484 KB |
Output is correct |
| 5 |
Correct |
92 ms |
3720 KB |
Output is correct |
| 6 |
Correct |
105 ms |
5952 KB |
Output is correct |
| 7 |
Correct |
288 ms |
4776 KB |
Output is correct |
| 8 |
Correct |
357 ms |
5200 KB |
Output is correct |
| 9 |
Correct |
836 ms |
10800 KB |
Output is correct |
| 10 |
Correct |
1771 ms |
9148 KB |
Output is correct |
| 11 |
Correct |
4970 ms |
9492 KB |
Output is correct |
| 12 |
Correct |
5108 ms |
15268 KB |
Output is correct |
| 13 |
Execution timed out |
8015 ms |
11644 KB |
Time limit exceeded |
| 14 |
Execution timed out |
8031 ms |
12220 KB |
Time limit exceeded |
| 15 |
Execution timed out |
8066 ms |
49400 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1968 ms |
37136 KB |
Execution failed because the return code was nonzero |
| 2 |
Runtime error |
1896 ms |
26276 KB |
Execution failed because the return code was nonzero |
| 3 |
Runtime error |
1625 ms |
58844 KB |
Execution failed because the return code was nonzero |
| 4 |
Execution timed out |
8090 ms |
41716 KB |
Time limit exceeded |
| 5 |
Execution timed out |
8080 ms |
71900 KB |
Time limit exceeded |
| 6 |
Incorrect |
6979 ms |
89800 KB |
Output isn't correct |
| 7 |
Execution timed out |
8083 ms |
107068 KB |
Time limit exceeded |
| 8 |
Runtime error |
7905 ms |
131076 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
872 ms |
131076 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
740 ms |
131076 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
724 ms |
131076 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
794 ms |
131076 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
790 ms |
131076 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
715 ms |
131076 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
723 ms |
131076 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
730 ms |
131076 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
712 ms |
131076 KB |
Execution killed with signal 9 |
