oj.uz

답안 #861983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861983 2023-10-17T10:24:01 Z parlimoos Regions (IOI09_regions) C++14
100 / 100
 2715 ms 29584 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: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 3 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 10 ms 9720 KB Output is correct
7 Correct 14 ms 9560 KB Output is correct
8 Correct 15 ms 9816 KB Output is correct
9 Correct 33 ms 10072 KB Output is correct
10 Correct 49 ms 10072 KB Output is correct
11 Correct 76 ms 10328 KB Output is correct
12 Correct 87 ms 10708 KB Output is correct
13 Correct 96 ms 10376 KB Output is correct
14 Correct 185 ms 11208 KB Output is correct
15 Correct 224 ms 12700 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1302 ms 17776 KB Output is correct
2 Correct 1237 ms 16580 KB Output is correct
3 Correct 2153 ms 18904 KB Output is correct
4 Correct 152 ms 11096 KB Output is correct
5 Correct 246 ms 12100 KB Output is correct
6 Correct 339 ms 20420 KB Output is correct
7 Correct 1102 ms 17316 KB Output is correct
8 Correct 731 ms 29032 KB Output is correct
9 Correct 1655 ms 17500 KB Output is correct
10 Correct 2715 ms 29584 KB Output is correct
11 Correct 2703 ms 17312 KB Output is correct
12 Correct 958 ms 21044 KB Output is correct
13 Correct 1287 ms 20836 KB Output is correct
14 Correct 1371 ms 23000 KB Output is correct
15 Correct 2184 ms 24272 KB Output is correct
16 Correct 2111 ms 27420 KB Output is correct
17 Correct 2108 ms 28596 KB Output is correct