oj.uz

답안 #477014

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477014 2021-09-29T18:17:18 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 = 300 #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 50 ms 18412 KB Output is correct
2 Correct 50 ms 18364 KB Output is correct
3 Correct 61 ms 18580 KB Output is correct
4 Correct 89 ms 20236 KB Output is correct
5 Correct 132 ms 21884 KB Output is correct
6 Correct 233 ms 27352 KB Output is correct
7 Correct 282 ms 27580 KB Output is correct
8 Correct 338 ms 29796 KB Output is correct
9 Correct 443 ms 33440 KB Output is correct
10 Correct 545 ms 30424 KB Output is correct
11 Correct 652 ms 32816 KB Output is correct
12 Correct 818 ms 36764 KB Output is correct
13 Correct 1184 ms 34556 KB Output is correct
14 Correct 857 ms 37236 KB Output is correct
15 Correct 1049 ms 78928 KB Output is correct

Subtask #2
25.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5678 ms 57024 KB Output is correct
2 Correct 4794 ms 82352 KB Output is correct
3 Execution timed out 8095 ms 92856 KB Time limit exceeded
4 Correct 1008 ms 66232 KB Output is correct
5 Correct 1833 ms 85784 KB Output is correct
6 Correct 2171 ms 106232 KB Output is correct
7 Runtime error 549 ms 131076 KB Execution killed with signal 9
8 Runtime error 645 ms 131076 KB Execution killed with signal 9
9 Runtime error 590 ms 131076 KB Execution killed with signal 9
10 Runtime error 121 ms 131076 KB Execution killed with signal 9
11 Runtime error 117 ms 131076 KB Execution killed with signal 9
12 Runtime error 576 ms 131076 KB Execution killed with signal 9
13 Runtime error 580 ms 131076 KB Execution killed with signal 9
14 Runtime error 171 ms 131076 KB Execution killed with signal 9
15 Runtime error 116 ms 131076 KB Execution killed with signal 9
16 Runtime error 112 ms 131076 KB Execution killed with signal 9
17 Runtime error 179 ms 131076 KB Execution killed with signal 9