oj.uz

Submission #556320

# Submission time Handle Problem Language Result Execution time Memory
556320 2022-05-02T21:35:07 Z GioChkhaidze Regions (IOI09_regions) C++14
100 / 100
 3107 ms 104452 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][800], cur[800];

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 = 200;
	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 4 ms 5584 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 9 ms 5584 KB Output is correct
5 Correct 8 ms 5584 KB Output is correct
6 Correct 19 ms 5712 KB Output is correct
7 Correct 27 ms 5716 KB Output is correct
8 Correct 35 ms 5712 KB Output is correct
9 Correct 49 ms 6080 KB Output is correct
10 Correct 82 ms 6096 KB Output is correct
11 Correct 115 ms 6480 KB Output is correct
12 Correct 137 ms 6992 KB Output is correct
13 Correct 178 ms 6676 KB Output is correct
14 Correct 238 ms 7272 KB Output is correct
15 Correct 294 ms 10576 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1192 ms 11080 KB Output is correct
2 Correct 752 ms 10016 KB Output is correct
3 Correct 2740 ms 13160 KB Output is correct
4 Correct 245 ms 7248 KB Output is correct
5 Correct 336 ms 8956 KB Output is correct
6 Correct 487 ms 28592 KB Output is correct
7 Correct 981 ms 40900 KB Output is correct
8 Correct 904 ms 46024 KB Output is correct
9 Correct 1629 ms 58864 KB Output is correct
10 Correct 1882 ms 96840 KB Output is correct
11 Correct 1498 ms 92016 KB Output is correct
12 Correct 1028 ms 64072 KB Output is correct
13 Correct 1367 ms 64296 KB Output is correct
14 Correct 2054 ms 72536 KB Output is correct
15 Correct 3107 ms 99036 KB Output is correct
16 Correct 1660 ms 104452 KB Output is correct
17 Correct 2855 ms 81716 KB Output is correct