Submission #476912

# Submission time Handle Problem Language Result Execution time Memory
476912 2021-09-29T04:55:05 Z fufu Regions (IOI09_regions) PyPy 3
17 / 100
1719 ms 131076 KB
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 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
# Verdict Execution time Memory 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