Submission #476917

# Submission time Handle Problem Language Result Execution time Memory
476917 2021-09-29T05:05:53 Z fufu Regions (IOI09_regions) PyPy 3
25 / 100
2181 ms 131076 KB
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()
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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