Submission #861988

#	Time	Username	Problem	Language	Result	Execution time	Memory
861988		parlimoos	Regions (IOI09_regions)	C++14	100 / 100	2703 ms	58440 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 = 250;
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:4: 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:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |  sc("%i" , &d);
      |    ^
regions.cpp:108:5: 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:5: 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