oj.uz

답안 #862199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862199 2023-10-17T16:47:15 Z parlimoos Regions (IOI09_regions) C++14
100 / 100
 2730 ms 57628 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 pp pop_back
#define pr printf
#define sc scanf
#define endl pr("\n")
#define debug(x) pr("%s , %i\n" , #x , x)
#define bg begin
#define arr(x) array<int , (x)>
#define flush fflush(stdout)
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[25000];
int ps[200000];

int timer = -1;
void dfs(int v = 0){
	times[v][0] = ++timer;
	tour[wrg[v]].pb(timer);
	for(int u : g[v]) dfs(u);
	times[v][1] = timer;
}
void bfs(int e){
	queue<arr(3)> que;
	que.push({0 , -1 , 0});
	
	while(!que.empty()){
		auto d = que.front();
		que.pop();
		if(d[0] != 0 and wrg[d[1]] == e) d[2]++;
		mem[rginx[e]][wrg[d[0]]] += d[2];
		for(int u : g[d[0]]) que.push({u , d[0] , d[2]});
	}
}
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++;
			bfs(i);
		}
	}
}
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;
	}
	
	dfs();
	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:94:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  sc("%i%i%i" , &n , &r , &q);
      |    ^
regions.cpp:96:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  sc("%i" , &d);
      |    ^
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" , &p , &d);
      |     ^
regions.cpp:111:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   sc("%i%i" , &a , &b);
      |     ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8792 KB Output is correct
4 Correct 4 ms 8792 KB Output is correct
5 Correct 6 ms 8792 KB Output is correct
6 Correct 10 ms 9048 KB Output is correct
7 Correct 14 ms 9048 KB Output is correct
8 Correct 16 ms 9048 KB Output is correct
9 Correct 23 ms 9304 KB Output is correct
10 Correct 44 ms 9304 KB Output is correct
11 Correct 72 ms 9560 KB Output is correct
12 Correct 75 ms 10072 KB Output is correct
13 Correct 99 ms 9816 KB Output is correct
14 Correct 178 ms 10240 KB Output is correct
15 Correct 202 ms 12200 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1285 ms 16720 KB Output is correct
2 Correct 814 ms 21820 KB Output is correct
3 Correct 2103 ms 16044 KB Output is correct
4 Correct 154 ms 10328 KB Output is correct
5 Correct 246 ms 11296 KB Output is correct
6 Correct 330 ms 19364 KB Output is correct
7 Correct 672 ms 18456 KB Output is correct
8 Correct 696 ms 28076 KB Output is correct
9 Correct 1387 ms 29224 KB Output is correct
10 Correct 2044 ms 32768 KB Output is correct
11 Correct 2730 ms 57628 KB Output is correct
12 Correct 930 ms 19892 KB Output is correct
13 Correct 1268 ms 20200 KB Output is correct
14 Correct 1485 ms 22096 KB Output is correct
15 Correct 2247 ms 23364 KB Output is correct
16 Correct 2029 ms 26316 KB Output is correct
17 Correct 2019 ms 27896 KB Output is correct