oj.uz

Submission #492342

# Submission time Handle Problem Language Result Execution time Memory
492342 2021-12-06T21:33:04 Z keta_tsimakuridze Regions (IOI09_regions) C++14
100 / 100
 6935 ms 95572 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, Bl = 505, n, r, q, c[N],idx = 0, tmin[N], tmout[N], id[N];
vector<int> heavy_p[25005], V[N];
vector<int> comp[N], x;
set<pii> occ[N];
void dfs(int u,int p) {
	tmin[u] = ++t;
	x[id[c[u]]]++;occ[c[u]].insert({tmin[u], occ[c[u]].size()});
	for(int i = 0; i < V[u].size(); i++) {
		dfs(V[u][i], u);
	}
	x[id[c[u]]]--;
	for(int i = 0; i < x.size(); i++) {
		heavy_p[c[u]][i] += x[i];
	}
	
	tmout[u] = t;
}
main(){
	cin >> n >> r >> q;
	cin >> c[1];
	for(int i = 2; i <= n; i++) {
		int p;
		cin >> p >> c[i];
		V[p].push_back(i);
	}
	for(int i = 1; i <= n; i++) {
		comp[c[i]].push_back(i);
	}
	idx = 0;
	for(int i = 1; i <= r; i++) {
		if(comp[i].size() >= Bl) {
			id[i] = ++idx;
		}
	}
	for(int i = 1; i <= r; i++) {
		heavy_p[i].resize(n/Bl + 2);
		occ[i].insert({0, 0});
	}
	x.resize(n/Bl + 2);
	dfs(1, 0);
	for(int i = 1; i <= r; i++) {
		occ[i].insert({n + 1, occ[i].size()});
	}
	while(q--) {
		int r1,r2;
		cin >> r1 >> r2;
		if(comp[r1].size() >= Bl) {
			cout << heavy_p[r2][id[r1]] << endl;
		}
		else {
			int ans = 0;
			for(int i = 0; i < comp[r1].size(); i++) {
				int l = tmin[comp[r1][i]], r = tmout[comp[r1][i]];
				ans += ((*occ[r2].upper_bound({r, n + 1})).s - 1 - (*--occ[r2].upper_bound({l - 1, n + 1})).s);
			}
			cout << ans << endl;
		}
	}
}

Compilation message

regions.cpp: In function 'void dfs(int, int)':
regions.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
regions.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main(){
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:37:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |   if(comp[i].size() >= Bl) {
      |      ~~~~~~~~~~~~~~~^~~~~
regions.cpp:53:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |   if(comp[r1].size() >= Bl) {
      |      ~~~~~~~~~~~~~~~~^~~~~
regions.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int i = 0; i < comp[r1].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19656 KB Output is correct
2 Correct 10 ms 19648 KB Output is correct
3 Correct 12 ms 19656 KB Output is correct
4 Correct 14 ms 19656 KB Output is correct
5 Correct 18 ms 19656 KB Output is correct
6 Correct 27 ms 19824 KB Output is correct
7 Correct 39 ms 19784 KB Output is correct
8 Correct 42 ms 19884 KB Output is correct
9 Correct 50 ms 20552 KB Output is correct
10 Correct 63 ms 20680 KB Output is correct
11 Correct 162 ms 21152 KB Output is correct
12 Correct 185 ms 21928 KB Output is correct
13 Correct 222 ms 21704 KB Output is correct
14 Correct 381 ms 22464 KB Output is correct
15 Correct 397 ms 26740 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2541 ms 27888 KB Output is correct
2 Correct 2742 ms 26560 KB Output is correct
3 Correct 4018 ms 31092 KB Output is correct
4 Correct 311 ms 23876 KB Output is correct
5 Correct 440 ms 27200 KB Output is correct
6 Correct 1778 ms 28352 KB Output is correct
7 Correct 2190 ms 33108 KB Output is correct
8 Correct 1926 ms 43672 KB Output is correct
9 Correct 3284 ms 54736 KB Output is correct
10 Correct 6586 ms 78900 KB Output is correct
11 Correct 6935 ms 78248 KB Output is correct
12 Correct 2286 ms 63364 KB Output is correct
13 Correct 3285 ms 64100 KB Output is correct
14 Correct 3023 ms 71796 KB Output is correct
15 Correct 5121 ms 86172 KB Output is correct
16 Correct 5166 ms 95572 KB Output is correct
17 Correct 4841 ms 85212 KB Output is correct