oj.uz

Submission #492344

# Submission time Handle Problem Language Result Execution time Memory
492344 2021-12-06T21:36:56 Z keta_tsimakuridze Regions (IOI09_regions) C++14
100 / 100
 7400 ms 105772 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 = 400, 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 19656 KB Output is correct
3 Correct 10 ms 19684 KB Output is correct
4 Correct 15 ms 19656 KB Output is correct
5 Correct 15 ms 19656 KB Output is correct
6 Correct 28 ms 19784 KB Output is correct
7 Correct 31 ms 19784 KB Output is correct
8 Correct 44 ms 19912 KB Output is correct
9 Correct 57 ms 20488 KB Output is correct
10 Correct 98 ms 20676 KB Output is correct
11 Correct 117 ms 21192 KB Output is correct
12 Correct 181 ms 22000 KB Output is correct
13 Correct 227 ms 21704 KB Output is correct
14 Correct 372 ms 22424 KB Output is correct
15 Correct 397 ms 26816 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2415 ms 28020 KB Output is correct
2 Correct 2787 ms 26652 KB Output is correct
3 Correct 3844 ms 31108 KB Output is correct
4 Correct 332 ms 24144 KB Output is correct
5 Correct 438 ms 27564 KB Output is correct
6 Correct 547 ms 29180 KB Output is correct
7 Correct 1643 ms 34488 KB Output is correct
8 Correct 1370 ms 45632 KB Output is correct
9 Correct 2947 ms 59096 KB Output is correct
10 Correct 3818 ms 88000 KB Output is correct
11 Correct 7400 ms 88492 KB Output is correct
12 Correct 2611 ms 69740 KB Output is correct
13 Correct 3152 ms 70404 KB Output is correct
14 Correct 3660 ms 80100 KB Output is correct
15 Correct 5055 ms 96308 KB Output is correct
16 Correct 4864 ms 105772 KB Output is correct
17 Correct 4698 ms 93340 KB Output is correct