oj.uz

답안 #862198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862198 2023-10-17T16:43:36 Z parlimoos Regions (IOI09_regions) C++14
25 / 100
 214 ms 131072 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][inroot];

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(2)> que;
	que.push({0 , -1});
	
	while(!que.empty()){
		auto d = que.front();
		que.pop();
		if(d[0] != 0){
			ps[d[0]][rginx[e]] = ps[d[1]][rginx[e]];
			if(wrg[d[1]] == e) ps[d[0]][rginx[e]]++;
		}
		mem[rginx[e]][wrg[d[0]]] += ps[d[0]][rginx[e]];
		for(int u : g[d[0]]) que.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++;
			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:97:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  sc("%i%i%i" , &n , &r , &q);
      |    ^
regions.cpp:99:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |  sc("%i" , &d);
      |    ^
regions.cpp:104:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   sc("%i%i" , &p , &d);
      |     ^
regions.cpp:114:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   sc("%i%i" , &a , &b);
      |     ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9304 KB Output is correct
2 Correct 2 ms 9304 KB Output is correct
3 Correct 3 ms 9304 KB Output is correct
4 Correct 4 ms 9304 KB Output is correct
5 Correct 6 ms 9304 KB Output is correct
6 Correct 11 ms 9304 KB Output is correct
7 Correct 16 ms 9304 KB Output is correct
8 Correct 18 ms 9304 KB Output is correct
9 Correct 26 ms 9560 KB Output is correct
10 Correct 46 ms 9812 KB Output is correct
11 Correct 78 ms 9848 KB Output is correct
12 Correct 88 ms 10200 KB Output is correct
13 Correct 110 ms 10068 KB Output is correct
14 Correct 203 ms 10584 KB Output is correct
15 Correct 212 ms 12376 KB Output is correct

Subtask #2
10.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 50 ms 131072 KB Execution killed with signal 9
2 Runtime error 50 ms 131072 KB Execution killed with signal 9
3 Runtime error 51 ms 131072 KB Execution killed with signal 9
4 Correct 164 ms 10664 KB Output is correct
5 Correct 214 ms 11884 KB Output is correct
6 Runtime error 48 ms 131072 KB Execution killed with signal 9
7 Runtime error 54 ms 131072 KB Execution killed with signal 9
8 Runtime error 55 ms 131072 KB Execution killed with signal 9
9 Runtime error 78 ms 131072 KB Execution killed with signal 9
10 Runtime error 72 ms 131072 KB Execution killed with signal 9
11 Runtime error 91 ms 131072 KB Execution killed with signal 9
12 Runtime error 96 ms 131072 KB Execution killed with signal 9
13 Runtime error 84 ms 131072 KB Execution killed with signal 9
14 Runtime error 106 ms 131072 KB Execution killed with signal 9
15 Runtime error 93 ms 131072 KB Execution killed with signal 9
16 Runtime error 96 ms 131072 KB Execution killed with signal 9
17 Runtime error 92 ms 131072 KB Execution killed with signal 9