Submission #476911

# Submission time Handle Problem Language Result Execution time Memory
476911 2021-09-29T04:21:09 Z fufu Regions (IOI09_regions) Python 3
10 / 100
8000 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 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
# Verdict Execution time Memory 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