oj.uz

답안 #682922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682922 2023-01-17T09:13:09 Z Phuong0703 Regions (IOI09_regions) C++14
55 / 100
 8000 ms 45128 KB 
/*
	Cred : SunnyYeahBoi
	Currently Coding at school :>
	Problem : 
*/

#include<bits/stdc++.h>

using namespace std;

//#define int long long
//#define double long double
//#define endl '\n'

const int MAXN = 200005;
const int MAXR = 25005;
const int INF = INT_MAX;
const int MOD = 1e9 + 7;

int pow_mod(int a , int b){
    a %= MOD;
    
    if(b == 0) return 1;
    if(b == 1) return a;
    
    int tmp = pow_mod(a , b / 2);
    
    if(b % 2 == 0)
        return (tmp * tmp) % MOD;
    else return ((tmp * tmp) % MOD * a) % MOD;
}

int numNodes , numCol , numQueries;
vector<int> Color_Index[MAXR];
vector<int> Idx[MAXN];
vector<int> g[MAXN];
vector<int> ans[MAXN];
int st[MAXN] , ed[MAXN] , timeDFS = 0;
vector<int> suf_sum[MAXN];

bool cmp(int a , int b){
	return st[a] < st[b];
}

bool cmp2(int a , int b){
	return a < st[b];
}

bool cmp3(int a , int b){
	return st[a] < b;
}

void DFS(int u , int par = -1){
	timeDFS++;
	st[u] = timeDFS;
	for(auto v : g[u]){
		if(v == par) continue;
		DFS(v , u);
	}
	ed[u] = timeDFS;
}

int BLOCK_SIZE;

void solve(){
	cin >> numNodes >> numCol >> numQueries;
	
	BLOCK_SIZE = sqrt(numNodes) + 5;
	
	{
		int x;
		cin >> x;
		Color_Index[x].push_back(1);
	}
	
	for(int i = 2 ; i <= numNodes ; i++){
		int col , par;
		cin >> par >> col;
		g[par].push_back(i);
		g[i].push_back(par);
		Color_Index[col].push_back(i);
	}
	// Read the Input
	
	DFS(1);
	
	st[numNodes + 1] = INF;
	st[numNodes + 2] = -INF;
	
	for(int i = 1 ; i <= numCol ; i++){
		Color_Index[i].push_back(numNodes + 1);
		Color_Index[i].push_back(numNodes + 2);
		Idx[i] = Color_Index[i];
		for(int j = 0 ; j < Idx[i].size() ; j++) Idx[i][j] = st[Idx[i][j]];
		sort(Idx[i].begin() , Idx[i].end());
		
		suf_sum[i].resize(Color_Index[i].size());
		suf_sum[i][suf_sum[i].size() - 1] = 0;
		for(int j = (int)suf_sum[i].size() - 2 ; j >= 1 ; j--)
			suf_sum[i][j] = suf_sum[i][j + 1] + 1;
		suf_sum[i][0] = suf_sum[i][1];
	}
	
	for(int i = 1 ; i <= numCol ; i++){
		vector<int> pref_sum(numNodes + 1 , 0);
		for(auto x : Idx[i])
			if(x > 0 && x <= numNodes)pref_sum[x] += 1;
		for(int j = 1 ; j <= numNodes ; j++)
			pref_sum[j] = pref_sum[j - 1] + pref_sum[j];
	
		for(int j = 1 ; j <= numCol ; j++){
			if(Idx[j].size() < BLOCK_SIZE) continue;
			
			if(j == i) continue;
			if(ans[j].size() == 0) ans[j].resize(numCol + 5 , 0);
			
			for(auto x : Color_Index[j]){
				if(x == numNodes + 1 || x == numNodes + 2) continue;
				ans[j][i] += pref_sum[ed[x]] - pref_sum[st[x] - 1];
			}
		}	
	}
	
	// for(int i = 1 ; i <= numNodes ; i++){
		// if(Color_Index[i].size() == 0) continue;
		// cout << "Color : " << i << endl;
		// for(auto x : Idx[i])
			// cout << x << " ";
		// cout << endl;
	// }

	while(numQueries--){
		int r1 , r2;
		cin >> r1 >> r2;
		
		if(ans[r1].size() > 0){
			cout << ans[r1][r2] << endl;
		}else{
			int res = 0;
			for(auto x : Color_Index[r1]){
				if(x == numNodes + 1 || x == numNodes + 2) continue;
				
				int l = lower_bound(Idx[r2].begin() , Idx[r2].end() , st[x]) - Idx[r2].begin();
				int r = upper_bound(Idx[r2].begin() , Idx[r2].end() , ed[x]) - Idx[r2].begin() - 1;
			
				//cout << r1 << " " << r2 << " " << st[x] << " " << ed[x] << " " << l << " " << r << " " << suf_sum[r2][l] - suf_sum[r2][r + 1] << endl;
			
				res += max(0 , suf_sum[r2][l] - suf_sum[r2][r + 1]);
			}
			
			cout << res << endl;
		}
	}
}

int32_t main(){
	//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// freopen(".INP" , "r" , stdin);
	// freopen(".OUT" , "w" , stdout);
	solve();
	return 0;
}

Compilation message

regions.cpp: In function 'void solve()':
regions.cpp:94:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for(int j = 0 ; j < Idx[i].size() ; j++) Idx[i][j] = st[Idx[i][j]];
      |                   ~~^~~~~~~~~~~~~~~
regions.cpp:112:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |    if(Idx[j].size() < BLOCK_SIZE) continue;
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19744 KB Output is correct
2 Correct 12 ms 19692 KB Output is correct
3 Correct 13 ms 19664 KB Output is correct
4 Correct 17 ms 19664 KB Output is correct
5 Correct 19 ms 19704 KB Output is correct
6 Correct 29 ms 19664 KB Output is correct
7 Correct 40 ms 19664 KB Output is correct
8 Correct 46 ms 19792 KB Output is correct
9 Correct 63 ms 20220 KB Output is correct
10 Correct 125 ms 20228 KB Output is correct
11 Correct 163 ms 20560 KB Output is correct
12 Correct 205 ms 21048 KB Output is correct
13 Correct 213 ms 21116 KB Output is correct
14 Correct 291 ms 21444 KB Output is correct
15 Correct 319 ms 23844 KB Output is correct

Subtask #2
40.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1782 ms 24584 KB Output is correct
2 Correct 2029 ms 24360 KB Output is correct
3 Correct 3021 ms 26340 KB Output is correct
4 Correct 618 ms 21704 KB Output is correct
5 Correct 891 ms 23356 KB Output is correct
6 Correct 2356 ms 24980 KB Output is correct
7 Correct 3957 ms 26460 KB Output is correct
8 Correct 5987 ms 33136 KB Output is correct
9 Execution timed out 8036 ms 30256 KB Time limit exceeded
10 Execution timed out 8032 ms 45128 KB Time limit exceeded
11 Execution timed out 8061 ms 33208 KB Time limit exceeded
12 Execution timed out 8029 ms 31712 KB Time limit exceeded
13 Execution timed out 8026 ms 32432 KB Time limit exceeded
14 Execution timed out 8042 ms 34476 KB Time limit exceeded
15 Execution timed out 8035 ms 35952 KB Time limit exceeded
16 Execution timed out 8023 ms 41488 KB Time limit exceeded
17 Execution timed out 8029 ms 41840 KB Time limit exceeded