Submission #476914

#	Time	Username	Problem	Language	Result	Execution time	Memory
476914		fufu	Regions (IOI09_regions)	Cpython 3	12 / 100	8090 ms	131076 KiB

regions

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

• Subtask 1: 12 / 15
• Subtask 2: 0 / 85