제출 #682914

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
682914		Phuong0703	Regions (IOI09_regions)	C++14	60 / 100	8098 ms	40612 KiB

regions

/*
	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);
	
	{
		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++){
		if(Color_Index[i].size() < BLOCK_SIZE)
			continue;
			
		ans[i].resize(numCol + 1 , 0);
			
		for(auto x : Color_Index[i]){
			if(x == numNodes + 1 || x == numNodes + 2) continue;
			
			for(int j = 1 ; j <= numCol ; j++){
				
				if(j == i) continue;
				
				int l = lower_bound(Idx[j].begin() , Idx[j].end() , st[x]) - Idx[j].begin();
				int r = upper_bound(Idx[j].begin() , Idx[j].end() , ed[x]) - Idx[j].begin() - 1;
			
				ans[i][j] += max(0 , suf_sum[j][l] - suf_sum[j][r + 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;
}

컴파일 시 표준 에러 (stderr) 메시지

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:105:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |   if(Color_Index[i].size() < BLOCK_SIZE)
      |      ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 45 / 85