oj.uz

답안 #861988

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861988 2023-10-17T10:30:01 Z parlimoos Regions (IOI09_regions) C++14
100 / 100
 2703 ms 58440 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 = 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

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9560 KB Output is correct
2 Correct 2 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 5 ms 9560 KB Output is correct
6 Correct 11 ms 9560 KB Output is correct
7 Correct 15 ms 9560 KB Output is correct
8 Correct 18 ms 9560 KB Output is correct
9 Correct 30 ms 10072 KB Output is correct
10 Correct 48 ms 10072 KB Output is correct
11 Correct 79 ms 10328 KB Output is correct
12 Correct 91 ms 10556 KB Output is correct
13 Correct 108 ms 10328 KB Output is correct
14 Correct 191 ms 10832 KB Output is correct
15 Correct 198 ms 12632 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1272 ms 17580 KB Output is correct
2 Correct 863 ms 22888 KB Output is correct
3 Correct 2219 ms 19500 KB Output is correct
4 Correct 164 ms 11092 KB Output is correct
5 Correct 218 ms 11992 KB Output is correct
6 Correct 308 ms 20436 KB Output is correct
7 Correct 759 ms 21324 KB Output is correct
8 Correct 690 ms 28876 KB Output is correct
9 Correct 1360 ms 29956 KB Output is correct
10 Correct 2069 ms 33884 KB Output is correct
11 Correct 2703 ms 58440 KB Output is correct
12 Correct 992 ms 20756 KB Output is correct
13 Correct 1284 ms 20788 KB Output is correct
14 Correct 1499 ms 22952 KB Output is correct
15 Correct 2284 ms 24220 KB Output is correct
16 Correct 2151 ms 27348 KB Output is correct
17 Correct 2050 ms 28916 KB Output is correct