oj.uz

답안 #477013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477013 2021-09-29T18:15:49 Z fufu Regions (IOI09_regions) PyPy 3
40 / 100
 8000 ms 131076 KB 
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 = 400 #sqrt const
	t = 0
	
	global p, l, r, bit, g
	a = [0] * n
	p = [0] * n
	l = [0] * n
	r = [0] * n
	bit = [0] * (n + 1)
	b = [0] * k
	f1 = [[0] * k for i in range(m)]
	f2 = [[0] * 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]) > n // m:
			dp = [0] * n
			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
			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
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 19976 KB Output is correct
2 Correct 46 ms 18452 KB Output is correct
3 Correct 61 ms 18708 KB Output is correct
4 Correct 98 ms 20368 KB Output is correct
5 Correct 137 ms 22288 KB Output is correct
6 Correct 245 ms 26996 KB Output is correct
7 Correct 291 ms 27664 KB Output is correct
8 Correct 331 ms 29536 KB Output is correct
9 Correct 458 ms 35388 KB Output is correct
10 Correct 553 ms 35812 KB Output is correct
11 Correct 628 ms 32988 KB Output is correct
12 Correct 730 ms 39504 KB Output is correct
13 Correct 803 ms 38416 KB Output is correct
14 Correct 874 ms 39296 KB Output is correct
15 Correct 1112 ms 81380 KB Output is correct

Subtask #2
25.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2493 ms 59328 KB Output is correct
2 Correct 2359 ms 80732 KB Output is correct
3 Execution timed out 8076 ms 92840 KB Time limit exceeded
4 Correct 1044 ms 72280 KB Output is correct
5 Correct 1627 ms 107408 KB Output is correct
6 Correct 1698 ms 115312 KB Output is correct
7 Runtime error 475 ms 131076 KB Execution killed with signal 9
8 Runtime error 491 ms 131076 KB Execution killed with signal 9
9 Runtime error 235 ms 131076 KB Execution killed with signal 9
10 Runtime error 104 ms 131076 KB Execution killed with signal 9
11 Runtime error 113 ms 131076 KB Execution killed with signal 9
12 Runtime error 122 ms 131076 KB Execution killed with signal 9
13 Runtime error 121 ms 131076 KB Execution killed with signal 9
14 Runtime error 104 ms 131076 KB Execution killed with signal 9
15 Runtime error 107 ms 131076 KB Execution killed with signal 9
16 Runtime error 104 ms 131076 KB Execution killed with signal 9
17 Runtime error 111 ms 131076 KB Execution killed with signal 9