oj.uz

답안 #764194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764194 2023-06-23T08:30:52 Z a_aguilo Regions (IOI09_regions) C++14
40 / 100
 8000 ms 25276 KB 
#include<bits/stdc++.h>

using namespace std;

int N, R, Q;
int SQRT = 450;
int region[200000];
vector<vector<int>> AdjList;
vector<int> EulerTours;
int enter[200000];
int out[200000];
//unordered_map<int, int> freqRegions;

void dfs(int node){
	//cout << node << endl;
	EulerTours.push_back(node);
	enter[node] = EulerTours.size()-1;
	for(int son: AdjList[node]){
		dfs(son);
	}
	out[node] = EulerTours.size()-1;
}

/*

void rSmall(){
	int r;
	freqRegions.reserve(512);
	vector<vector<int>> dp(R, vector<int>(R, 0));
	preProcess(0, dp);
	int r1, r2;
	while(Q--){
		cin >> r1 >> r2;
		r1--; r2--;
		cout << dp[r1][r2] << endl;
	}
}*/

void rBig(){
	//vector<map<int, int>> blocks(500);
	vector<vector<int>> employees(R);
	for(int i = 0; i < N; ++i){
		employees[region[i]].push_back(i);
		int B = i/SQRT;
		//blocks[R][region[EulerTours[i]]]++;
	}
	int r1, r2;
	while(Q--){
		cin >> r1 >> r2;
		r1--; r2--;
		int ans = 0;
		for(int i: employees[r1]){
			for(int j: employees[r2]){
				if(enter[i]<enter[j] && out[i]>=out[j])ans++;
			}
		}
		cout << ans << endl;
	}
}

int main(){
	int p;
	cin >> N >> R >> Q;
	AdjList = vector<vector<int>>(N);
	for(int i = 0; i < N; ++i){
		
		if(i){
			cin >> p;
			p--;
			AdjList[p].push_back(i);
		}
		cin >> region[i];
		region[i]--;
	}
	dfs(0);
	/*
	for(int i = 0; i < N; ++i) cout << EulerTours[i] << " ";
		cout << endl;*/
	/*
	if(R <= 1000) rSmall();
	else rBig();*/
	rBig();
	return 0;
}

Compilation message

regions.cpp: In function 'void rBig()':
regions.cpp:44:7: warning: unused variable 'B' [-Wunused-variable]
   44 |   int B = i/SQRT;
      |       ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 12 ms 336 KB Output is correct
7 Correct 28 ms 336 KB Output is correct
8 Correct 33 ms 464 KB Output is correct
9 Correct 48 ms 848 KB Output is correct
10 Correct 76 ms 1104 KB Output is correct
11 Correct 147 ms 1428 KB Output is correct
12 Correct 196 ms 2000 KB Output is correct
13 Correct 285 ms 1736 KB Output is correct
14 Correct 630 ms 2552 KB Output is correct
15 Correct 659 ms 5308 KB Output is correct

Subtask #2
25.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8064 ms 6592 KB Time limit exceeded
2 Execution timed out 8023 ms 5576 KB Time limit exceeded
3 Execution timed out 8061 ms 8768 KB Time limit exceeded
4 Correct 280 ms 2640 KB Output is correct
5 Correct 368 ms 4488 KB Output is correct
6 Execution timed out 8019 ms 4476 KB Time limit exceeded
7 Correct 4362 ms 5896 KB Output is correct
8 Correct 2547 ms 11496 KB Output is correct
9 Correct 4019 ms 13012 KB Output is correct
10 Execution timed out 8061 ms 18492 KB Time limit exceeded
11 Execution timed out 8023 ms 14012 KB Time limit exceeded
12 Execution timed out 8093 ms 15304 KB Time limit exceeded
13 Execution timed out 8076 ms 15564 KB Time limit exceeded
14 Execution timed out 8079 ms 15552 KB Time limit exceeded
15 Execution timed out 8045 ms 19824 KB Time limit exceeded
16 Execution timed out 8007 ms 25276 KB Time limit exceeded
17 Execution timed out 8101 ms 24040 KB Time limit exceeded