oj.uz

답안 #862004

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862004 2023-10-17T11:00:42 Z parlimoos Regions (IOI09_regions) C++11
100 / 100
 2823 ms 59044 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 9 ms 9560 KB Output is correct
7 Correct 17 ms 9556 KB Output is correct
8 Correct 15 ms 9560 KB Output is correct
9 Correct 26 ms 10072 KB Output is correct
10 Correct 39 ms 10328 KB Output is correct
11 Correct 76 ms 10328 KB Output is correct
12 Correct 85 ms 10584 KB Output is correct
13 Correct 107 ms 10436 KB Output is correct
14 Correct 201 ms 11000 KB Output is correct
15 Correct 203 ms 12680 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1263 ms 17820 KB Output is correct
2 Correct 901 ms 22904 KB Output is correct
3 Correct 2130 ms 19044 KB Output is correct
4 Correct 165 ms 11096 KB Output is correct
5 Correct 216 ms 12132 KB Output is correct
6 Correct 318 ms 20192 KB Output is correct
7 Correct 777 ms 21340 KB Output is correct
8 Correct 711 ms 29140 KB Output is correct
9 Correct 1330 ms 30092 KB Output is correct
10 Correct 2130 ms 33644 KB Output is correct
11 Correct 2823 ms 59044 KB Output is correct
12 Correct 989 ms 21044 KB Output is correct
13 Correct 1371 ms 20760 KB Output is correct
14 Correct 1457 ms 22952 KB Output is correct
15 Correct 2405 ms 24220 KB Output is correct
16 Correct 2141 ms 27532 KB Output is correct
17 Correct 2060 ms 28520 KB Output is correct