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

regions

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()

Subtask #1

10.0 / 15.0

#	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

Subtask #2

0 / 85.0

#	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