oj.uz

Submission #764157

# Submission time Handle Problem Language Result Execution time Memory
764157 2023-06-23T07:54:36 Z a_aguilo Regions (IOI09_regions) C++14
4 / 100
 8000 ms 50000 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;
vector<int> visited;
int enter[200000];
int out[200000];
unordered_map<int, int> freqRegions;

void dfs(int node){
	visited[node] = 1;
	//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));
	pair<pair<int, int>, pair<int, int>> queries[N];
	for(int i = 0; i < N; ++i){
		queries[i] = {{enter[i]/SQRT, -out[i]}, {enter[i], i}};
	}
	sort(queries, queries+N);
	int left = 0; int right = 0;
	freqRegions[EulerTours[0]] = 1;
	for(int i = 0; i < N; ++i){
		int qR = - queries[i].first.second;
		int qL = queries[i].second.first;
		while(right < qR){
			right++;
			r = region[EulerTours[right]];
			freqRegions[r]++;
		}while(right > qR){
			r = region[EulerTours[right]];
			freqRegions[r]--;
			right--;
		}
		while(left < qL){
			r = region[EulerTours[left]];
			freqRegions[r]--;
			left++;
		}while(left > qL){
			left--;
			r = region[EulerTours[left]];
			freqRegions[r]++;
		}
		int actualReg = region[queries[i].second.second];
		for(int i = 0; i < R; ++i){
			dp[actualReg][i] += freqRegions[i];
		}
	}
	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]){
			int l = enter[i];
			int r = out[i];
			//cout << i << " " << l << " " << r << endl;
			while(l % SQRT != 0 and l <= r){
				if(region[EulerTours[l]] == r2)ans++;
				l++;
			}
			int bR = r/SQRT;
			while(bR*SQRT <= r and l<=r){
				if(region[EulerTours[r]] == r2) ans++;
				r--;
			}
			int bL = l/SQRT;
			while(bL < bR){
				ans += blocks[bL][r2];
				bL++;
			}
		}
		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]--;
	}
	visited = vector<int>(N, 0);
	dfs(0);
	/*
	for(int i = 0; i < N; ++i) cout << EulerTours[i] << " ";
		cout << endl;*/
	/*
	if(R <= 500) rSmall();
	else rBig();*/
	rBig();
	return 0;
}

Compilation message

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

Subtask #1
4.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Incorrect 6 ms 336 KB Output isn't correct
6 Incorrect 20 ms 464 KB Output isn't correct
7 Incorrect 32 ms 464 KB Output isn't correct
8 Incorrect 33 ms 544 KB Output isn't correct
9 Incorrect 139 ms 1080 KB Output isn't correct
10 Incorrect 95 ms 1464 KB Output isn't correct
11 Incorrect 254 ms 1976 KB Output isn't correct
12 Incorrect 730 ms 3080 KB Output isn't correct
13 Incorrect 189 ms 2684 KB Output isn't correct
14 Incorrect 468 ms 3276 KB Output isn't correct
15 Incorrect 5895 ms 6456 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8087 ms 8244 KB Time limit exceeded
2 Execution timed out 8006 ms 7396 KB Time limit exceeded
3 Execution timed out 8085 ms 11516 KB Time limit exceeded
4 Runtime error 16 ms 4944 KB Execution killed with signal 11
5 Runtime error 32 ms 8644 KB Execution killed with signal 11
6 Runtime error 27 ms 8632 KB Execution killed with signal 11
7 Runtime error 37 ms 11092 KB Execution killed with signal 11
8 Runtime error 68 ms 22404 KB Execution killed with signal 11
9 Runtime error 94 ms 24736 KB Execution killed with signal 11
10 Runtime error 110 ms 35952 KB Execution killed with signal 11
11 Runtime error 112 ms 26820 KB Execution killed with signal 11
12 Runtime error 114 ms 29952 KB Execution killed with signal 11
13 Runtime error 119 ms 30312 KB Execution killed with signal 11
14 Runtime error 118 ms 29928 KB Execution killed with signal 11
15 Runtime error 114 ms 38548 KB Execution killed with signal 11
16 Runtime error 123 ms 50000 KB Execution killed with signal 11
17 Runtime error 130 ms 47192 KB Execution killed with signal 11