Submission #861986

#	Time	Username	Problem	Language	Result	Execution time	Memory
861986		vjudge1	Regions (IOI09_regions)	C++14	100 / 100	2655 ms	29392 KiB

regions

#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 (stderr)

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 / 15
• Subtask 2: 85 / 85