oj.uz

답안 #764188

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764188 2023-06-23T08:27:18 Z a_aguilo Regions (IOI09_regions) C++14
15 / 100
 8000 ms 48384 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 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 17 ms 336 KB Output is correct
7 Correct 26 ms 464 KB Output is correct
8 Correct 36 ms 464 KB Output is correct
9 Correct 50 ms 976 KB Output is correct
10 Correct 92 ms 1104 KB Output is correct
11 Correct 167 ms 1488 KB Output is correct
12 Correct 155 ms 2128 KB Output is correct
13 Correct 310 ms 1872 KB Output is correct
14 Correct 748 ms 2592 KB Output is correct
15 Correct 604 ms 5352 KB Output is correct

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8096 ms 6612 KB Time limit exceeded
2 Execution timed out 8087 ms 5576 KB Time limit exceeded
3 Execution timed out 8055 ms 8784 KB Time limit exceeded
4 Runtime error 16 ms 4712 KB Execution killed with signal 11
5 Runtime error 20 ms 8432 KB Execution killed with signal 11
6 Runtime error 37 ms 8316 KB Execution killed with signal 11
7 Runtime error 37 ms 10564 KB Execution killed with signal 11
8 Runtime error 68 ms 21692 KB Execution killed with signal 11
9 Runtime error 100 ms 23624 KB Execution killed with signal 11
10 Runtime error 109 ms 34496 KB Execution killed with signal 11
11 Runtime error 127 ms 25180 KB Execution killed with signal 11
12 Runtime error 129 ms 28512 KB Execution killed with signal 11
13 Runtime error 104 ms 28824 KB Execution killed with signal 11
14 Runtime error 163 ms 28336 KB Execution killed with signal 11
15 Runtime error 115 ms 36968 KB Execution killed with signal 11
16 Runtime error 118 ms 48384 KB Execution killed with signal 11
17 Runtime error 114 ms 45668 KB Execution killed with signal 11