oj.uz

Submission #556317

# Submission time Handle Problem Language Result Execution time Memory
556317 2022-05-02T21:31:19 Z GioChkhaidze Regions (IOI09_regions) C++14
100 / 100
 3822 ms 75084 KB 
#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second

using namespace std;

const int N = 2e5 + 5;
const int M = 25005;

int sq;
bool Hv[M], Lh[M];
int n, r, q, timer;
vector < int > s, v[N], R[M];
int in[N], out[N], O[N], c[N], p[N], idx[M], G[M][500], cur[500];

bool is_anc(int a, int b) {
	return (in[a] <= in[b] && out[b] <= out[a]);
}

void dfs(int x) {
	in[x] = ++timer;
	O[timer] = x;
	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		dfs(to);  
	}
	out[x] = timer;
}

void wfs(int x) {
	int col = c[x];
	for (int i = 0; i < s.size(); ++i) {
		if (col == s[i]) continue;
		G[col][i] += cur[i];
	}
	
	if (Hv[col]) {
		++cur[idx[col]];
	}

	for (int i = 0; i < v[x].size(); ++i) {
		int to = v[x][i];
		wfs(to);  
	}
	
	if (Hv[col]) {
		--cur[idx[col]];
	}
}

main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> r >> q;
	cin >> c[1];
	for (int i = 2; i <= n; ++i) {
		cin >> p[i] >> c[i];
		v[p[i]].pb(i);
	}
	
	dfs(1);
	for (int i = 1; i <= n; ++i) {
		R[c[i]].pb(in[i]);
	}
	
	sq = sqrt(n);
	for (int i = 1; i <= r; ++i) {
		sort(R[i].begin(), R[i].end());
		if (R[i].size() > sq) {
			idx[i] = s.size();
			Hv[i] = true;
			s.pb(i);	
		}
			else {
			Lh[i] = true;
		}
	}
	
	wfs(1);
	for (int i = 1; i <= q; ++i) {
		int x, y, ans = 0;
		cin >> x >> y;
		if (Lh[x]) {
			for (int j = 0; j < R[x].size(); ++j) {
				int id = O[R[x][j]];
				int Rc = (lower_bound(R[y].begin(), R[y].end(), out[id] + 1) - R[y].begin());
				int Lc = (lower_bound(R[y].begin(), R[y].end(), in[id]) - R[y].begin());
				ans += Rc - Lc;
			}
		}
			else {
			ans = G[y][idx[x]];
		}
		cout << ans << endl;	
	} 
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
regions.cpp: In function 'void wfs(int)':
regions.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for (int i = 0; i < s.size(); ++i) {
      |                  ~~^~~~~~~~~~
regions.cpp:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for (int i = 0; i < v[x].size(); ++i) {
      |                  ~~^~~~~~~~~~~~~
regions.cpp: At global scope:
regions.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main () {
      | ^~~~
regions.cpp: In function 'int main()':
regions.cpp:71:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |   if (R[i].size() > sq) {
      |       ~~~~~~~~~~~~^~~~
regions.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    for (int j = 0; j < R[x].size(); ++j) {
      |                    ~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 8 ms 5712 KB Output is correct
6 Correct 13 ms 5712 KB Output is correct
7 Correct 32 ms 5712 KB Output is correct
8 Correct 29 ms 5712 KB Output is correct
9 Correct 44 ms 6096 KB Output is correct
10 Correct 67 ms 6096 KB Output is correct
11 Correct 87 ms 6480 KB Output is correct
12 Correct 128 ms 6992 KB Output is correct
13 Correct 142 ms 6608 KB Output is correct
14 Correct 235 ms 7692 KB Output is correct
15 Correct 212 ms 10320 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1722 ms 10804 KB Output is correct
2 Correct 2036 ms 9756 KB Output is correct
3 Correct 2699 ms 12844 KB Output is correct
4 Correct 206 ms 7248 KB Output is correct
5 Correct 344 ms 8900 KB Output is correct
6 Correct 502 ms 22088 KB Output is correct
7 Correct 973 ms 29128 KB Output is correct
8 Correct 956 ms 34272 KB Output is correct
9 Correct 2297 ms 14936 KB Output is correct
10 Correct 2853 ms 68800 KB Output is correct
11 Correct 3822 ms 14944 KB Output is correct
12 Correct 1114 ms 47424 KB Output is correct
13 Correct 1841 ms 47560 KB Output is correct
14 Correct 2073 ms 54952 KB Output is correct
15 Correct 2945 ms 69688 KB Output is correct
16 Correct 2751 ms 75084 KB Output is correct
17 Correct 2416 ms 63588 KB Output is correct