oj.uz

답안 #682914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682914 2023-01-17T08:50:46 Z Phuong0703 Regions (IOI09_regions) C++14
60 / 100
 8000 ms 40612 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);
	
	{
		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;
}

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: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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 19664 KB Output is correct
2 Correct 12 ms 19664 KB Output is correct
3 Correct 15 ms 19632 KB Output is correct
4 Correct 17 ms 19588 KB Output is correct
5 Correct 16 ms 19656 KB Output is correct
6 Correct 26 ms 19732 KB Output is correct
7 Correct 31 ms 19720 KB Output is correct
8 Correct 40 ms 19792 KB Output is correct
9 Correct 65 ms 20176 KB Output is correct
10 Correct 118 ms 20232 KB Output is correct
11 Correct 129 ms 20464 KB Output is correct
12 Correct 162 ms 20944 KB Output is correct
13 Correct 224 ms 20908 KB Output is correct
14 Correct 311 ms 21328 KB Output is correct
15 Correct 313 ms 23616 KB Output is correct

Subtask #2
45.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2021 ms 24300 KB Output is correct
2 Correct 2734 ms 24052 KB Output is correct
3 Correct 3520 ms 26116 KB Output is correct
4 Correct 345 ms 21600 KB Output is correct
5 Correct 400 ms 23112 KB Output is correct
6 Correct 5318 ms 24760 KB Output is correct
7 Correct 5678 ms 26104 KB Output is correct
8 Execution timed out 8063 ms 32576 KB Time limit exceeded
9 Correct 2251 ms 29604 KB Output is correct
10 Execution timed out 8036 ms 39324 KB Time limit exceeded
11 Correct 4287 ms 32424 KB Output is correct
12 Execution timed out 8098 ms 30892 KB Time limit exceeded
13 Execution timed out 8070 ms 31604 KB Time limit exceeded
14 Execution timed out 8029 ms 32176 KB Time limit exceeded
15 Execution timed out 8060 ms 35024 KB Time limit exceeded
16 Execution timed out 8055 ms 40612 KB Time limit exceeded
17 Execution timed out 8069 ms 39628 KB Time limit exceeded