oj.uz

답안 #477015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477015 2021-09-29T18:17:53 Z fufu Regions (IOI09_regions) PyPy 3
45 / 100
 3492 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 = 500 #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 65 ms 18436 KB Output is correct
2 Correct 53 ms 18560 KB Output is correct
3 Correct 88 ms 18736 KB Output is correct
4 Correct 104 ms 20336 KB Output is correct
5 Correct 164 ms 22572 KB Output is correct
6 Correct 326 ms 27448 KB Output is correct
7 Correct 281 ms 28308 KB Output is correct
8 Correct 371 ms 29092 KB Output is correct
9 Correct 377 ms 36700 KB Output is correct
10 Correct 638 ms 37520 KB Output is correct
11 Correct 636 ms 34472 KB Output is correct
12 Correct 754 ms 42804 KB Output is correct
13 Correct 874 ms 39444 KB Output is correct
14 Correct 904 ms 40420 KB Output is correct
15 Correct 1131 ms 82112 KB Output is correct

Subtask #2
30.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2432 ms 59484 KB Output is correct
2 Correct 2570 ms 59752 KB Output is correct
3 Correct 3492 ms 90540 KB Output is correct
4 Correct 930 ms 83496 KB Output is correct
5 Correct 1648 ms 119572 KB Output is correct
6 Correct 1665 ms 122220 KB Output is correct
7 Runtime error 391 ms 131076 KB Execution killed with signal 9
8 Runtime error 420 ms 131076 KB Execution killed with signal 9
9 Runtime error 116 ms 131076 KB Execution killed with signal 9
10 Runtime error 106 ms 131076 KB Execution killed with signal 9
11 Runtime error 111 ms 131076 KB Execution killed with signal 9
12 Runtime error 108 ms 131076 KB Execution killed with signal 9
13 Runtime error 118 ms 131076 KB Execution killed with signal 9
14 Runtime error 97 ms 131076 KB Execution killed with signal 9
15 Runtime error 100 ms 131076 KB Execution killed with signal 9
16 Runtime error 105 ms 131076 KB Execution killed with signal 9
17 Runtime error 119 ms 131076 KB Execution killed with signal 9