oj.uz

답안 #861986

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861986 2023-10-17T10:27:42 Z vjudge1 Regions (IOI09_regions) C++14
100 / 100
 2655 ms 29392 KB 
#pragma GCC optimize("Ofast")
	#include<bits/stdc++.h>
	using namespace std;
	
	#define pb push_back
	#define lb lower_bound
	#define ub upper_bound
	#define endl printf("\n")
	#define flush fflush(stdout)
	#define pp pop_back
	#define pr printf
	#define sc scanf
	#define debug(x) pr("%s , %i\n" , #x , x)
	#define bg begin
	#define arr(x) array<int , (x)>
	typedef long long ll;
	typedef pair<int , int> pii;
	typedef long double ld;
	const ll MOD = int(1e9) + 7;
	const int root = 450;
	const int inroot = 200000 / root + 1;
	
	ll Sum(ll a , ll b){
		ll res = a + b;
		if(res > MOD) return (res - MOD);
		if(res < 0) return (res + MOD);
		return res;
	}
	ll Mul(ll a , ll b){
		return (a * b) % MOD;
	}
	ll Pow(ll a , ll b){
	   ll res = 1;
	   while(b){
	   		if((b & 1)) res = Mul(res , a);
	   		a = Mul(a , a);
			b >>= 1;
	   }
	   return res;
	}
	
	int n , r , q;
	int wrg[200000];
	vector<int> rgs[25000];
	vector<int> g[200000];
	int times[200000][2];
	vector<int> tour[25000];
	int mem[inroot][25000];
	int rginx[200000];
	int ps[200000];
	
	int timer = -1;
	void dfs0(int v = 0){
		times[v][0] = ++timer;
		tour[wrg[v]].pb(timer);
		for(int u : g[v]) dfs0(u);
		times[v][1] = timer;
	}
	void bfs0(int e){
		fill(&ps[0] , &ps[n] , 0);
		queue<arr(2)> q;
		q.push({0 , -1});
		
		while(!q.empty()){
			auto d = q.front();
			q.pop();
			if(d[0] != 0){
				ps[d[0]] = ps[d[1]];
				if(wrg[d[1]] == e) ps[d[0]]++;
			}
			mem[rginx[e]][wrg[d[0]]] += ps[d[0]];
			for(int u : g[d[0]]){
				q.push({u , d[0]});
			}
		}
	}
	void init(){
		int counter = 0;
		for(int i = 0 ; i < r ; i++){
			if(!rgs[i].empty() and (int)rgs[i].size() > root){
				rginx[i] = counter;
				bfs0(i);
				counter++;
			}
		}
	}
	int f(int a , int c){
		int res = 0;
		for(int el : rgs[a]){
			if(times[el][0] == times[el][1]) continue;
			auto itr1 = ub(tour[c].bg() , tour[c].end() , times[el][0]);
			auto itr2 = ub(tour[c].bg() , tour[c].end() , times[el][1]);
			if(tour[c].empty() or itr2 == tour[c].bg()) continue;
			itr2--;
			res += int(itr2 - itr1 + 1);
		}
		return res;
	}
	
	int main(){
		sc("%i%i%i" , &n , &r , &q);
		int d;
		sc("%i" , &d);
		rgs[d - 1].pb(0);
		wrg[0] = d - 1;
		for(int i = 1 ; i < n ; i++){
			int p;
			sc("%i%i" , &p , &d);
			rgs[d - 1].pb(i);
			g[p - 1].pb(i);
			wrg[i] = d - 1;
		}
		
		dfs0();
		init();
		for(int i = 0 ; i < q ; i++){
			int a , b;
			sc("%i%i" , &a , &b);
			a-- , b--;
			
			if(rgs[a].empty()) pr("0\n");
			else if((int)rgs[a].size() <= root) pr("%i\n" , f(a , b));
			else pr("%i\n" , mem[rginx[a]][b]);
			flush;
		}
		
		/*
		ZZZZZZZ     A        M     M     IIIIIII  N     N
		     Z     A A      M M   M M       I     NN    N
		    Z     A   A    M   M M   M      I     N N   N
		   Z     AAAAAAA  M     M     M     I     N  N  N
		  Z      A     A  M           M     I     N   N N
		 Z       A     A  M           M     I     N    NN
		ZZZZZZZ  A     A  M           M  IIIIIII  N     N  TREE
		*/
	}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:101:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   sc("%i%i%i" , &n , &r , &q);
      |     ^
regions.cpp:103:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   sc("%i" , &d);
      |     ^
regions.cpp:108:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |    sc("%i%i" , &p , &d);
      |      ^
regions.cpp:118:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |    sc("%i%i" , &a , &b);
      |      ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 9560 KB Output is correct
2 Correct 3 ms 9560 KB Output is correct
3 Correct 3 ms 9560 KB Output is correct
4 Correct 4 ms 9560 KB Output is correct
5 Correct 6 ms 9560 KB Output is correct
6 Correct 10 ms 9560 KB Output is correct
7 Correct 13 ms 9560 KB Output is correct
8 Correct 21 ms 9816 KB Output is correct
9 Correct 25 ms 10072 KB Output is correct
10 Correct 44 ms 10324 KB Output is correct
11 Correct 74 ms 10216 KB Output is correct
12 Correct 91 ms 10584 KB Output is correct
13 Correct 108 ms 10396 KB Output is correct
14 Correct 197 ms 10840 KB Output is correct
15 Correct 205 ms 12696 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1338 ms 17772 KB Output is correct
2 Correct 1190 ms 16776 KB Output is correct
3 Correct 2181 ms 19116 KB Output is correct
4 Correct 159 ms 11092 KB Output is correct
5 Correct 218 ms 12252 KB Output is correct
6 Correct 340 ms 20468 KB Output is correct
7 Correct 1113 ms 17232 KB Output is correct
8 Correct 724 ms 29120 KB Output is correct
9 Correct 1675 ms 17884 KB Output is correct
10 Correct 2655 ms 29392 KB Output is correct
11 Correct 2598 ms 17252 KB Output is correct
12 Correct 908 ms 21048 KB Output is correct
13 Correct 1312 ms 20900 KB Output is correct
14 Correct 1456 ms 23008 KB Output is correct
15 Correct 2191 ms 24272 KB Output is correct
16 Correct 2060 ms 27584 KB Output is correct
17 Correct 2032 ms 28492 KB Output is correct