fork download
copy 
  1. import sys
  2. sys.setrecursionlimit(1 << 25)
  3. input = sys.stdin.readline
  4.  
  5. class BIT:
  6.     def __init__(self, n):
  7.         self.N = n + 2
  8.         self.tree = [0] * (self.N)
  9.     def update(self, idx, val):
  10.         while idx < self.N:
  11.             self.tree[idx] += val
  12.             idx += idx & -idx
  13.     def query(self, idx):
  14.         res = 0
  15.         while idx > 0:
  16.             res += self.tree[idx]
  17.             idx -= idx & -idx
  18.         return res
  19.     def range_add(self, l, r, val):
  20.         self.update(l, val)
  21.         self.update(r + 1, -val)
  22.  
  23. N, M = map(int, input().split())
  24.  
  25. # 트리 생성
  26. tree_joi = [[] for _ in range(N+1)]
  27. tree_ioi = [[] for _ in range(N+1)]
  28. root_j = root_i = 0
  29. for i in range(1, N+1):
  30.     Pj, Pi = map(int, input().split())
  31.     if Pj == 0:
  32.         root_j = i
  33.     else:
  34.         tree_joi[Pj].append(i)
  35.     if Pi == 0:
  36.         root_i = i
  37.     else:
  38.         tree_ioi[Pi].append(i)
  39.  
  40. # IOI 社 프로젝트 관련
  41. proj = [[] for _ in range(N+1)]
  42. for _ in range(M):
  43.     Rb, Sb = map(int, input().split())
  44.     proj[Sb].append(Rb)
  45.  
  46. # JOI 社 직원 Euler Tour
  47. tin = [0]*(N+1)
  48. tout = [0]*(N+1)
  49. time = 0
  50. def dfs_joi(u):
  51.     global time
  52.     time += 1
  53.     tin[u] = time
  54.     for v in tree_joi[u]:
  55.         dfs_joi(v)
  56.     tout[u] = time
  57. dfs_joi(root_j)
  58.  
  59. # BIT + DFS
  60. bit = BIT(N+2)
  61. ans = [0]*(N+1)
  62.  
  63. def dfs_ioi(u):
  64.     # 현재 IOI 社 직원 u가 리더인 프로젝트 처리
  65.     for r in proj[u]:
  66.         bit.range_add(tin[r], tout[r], 1)
  67.     # IOI 社 직원 u의 스파이 성공 횟수
  68.     ans[u] = bit.query(tin[u])
  69.     for v in tree_ioi[u]:
  70.         dfs_ioi(v)
  71.     # 되돌리기
  72.     for r in proj[u]:
  73.         bit.range_add(tin[r], tout[r], -1)
  74.  
  75. dfs_ioi(root_i)
  76.  
  77. for i in range(1, N+1):
  78.     print(ans[i])
Success #stdin #stdout 0.07s 14092KB
comments (?)
stdin
copy 
3 4
0 2
1 0
2 2
1 1
2 1
2 3
3 2
stdout
copy 
1
0
2
https://ideone.com/Nbd3il
language:
Python 3 (python  3.12)
created:
22 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!