oj.uz

Submission #477477

# Submission time Handle Problem Language Result Execution time Memory
477477 2021-10-02T09:09:49 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
0 / 100
 1864 ms 34816 KB 
#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n = MX;

    int sum(int r) {
    	if(bit.empty()) bit.resize(n);
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
    	if(bit.empty()) bit.resize(n);
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
const int B = 400;
int N, R, Q;
vector <int> g[MX], region[MX];
int H[MX], st[MX], en[MX], timer=1;
int found[MX];
map <int, vector <int>> prep;
void Flat(int v, int p) {
	st[v] = timer++;
	if(!found[H[v]]) {
		found[H[v]] = st[v];
		region[H[v]].push_back(v);
	}
	for(auto to : g[v]) if(to!=p) {
		Flat(to, v);
	}
	en[v] = timer-1;
	if(found[H[v]]==st[v]) {
		found[H[v]] = 0;
	}
}
int main() {
	cin >> N >> R >> Q;
	cin >> H[1];
	for(int i=2; i<=N; ++i) {
		int p; cin >> p >> H[i];
		g[p].push_back(i);
	}
	Flat(1, 1);
	vector <int> bigs;
	for(int i=1; i<=R; ++i) if(region[i].size()>B) {
		bigs.push_back(i);
	}
	int sz_big = bigs.size();
	FenwickTree A;
	for(int all=1; all<=25000; ++all) {
		for(auto it : region[all]) {
			A.add(st[it], 1);
		}
		for(auto b : bigs) {
			if(prep[b].empty()) prep[b].resize(25001);
			for(auto it : region[b]) {
				prep[b][all] = A.sum(st[it], en[it]);
			}
		}
		for(auto it : region[all]) {
			A.add(st[it], -1);
		}
	}
	map <int, FenwickTree> sb;
	for(auto b : bigs) {
		for(auto it : region[b]) {
			sb[b].add(st[it], 1);
		}
	}
	while(Q--) {
		int r1, r2;
		cin >> r1 >> r2;
		int ans = 0;
		if(region[r1].size()>B) {
			ans = prep[r1][r2];
		} else {
			if(region[r2].size()>B) {
				for(auto it : region[r1]) {
					ans += sb[r2].sum(st[it], en[it]);
				}
			} else {
				int p1 = 0, p2 = 0;
				while(p1<region[r1].size() && p2<region[r2].size()) {
					auto ok = [&] (int p1, int p2) {
						return st[region[r1][p1]]<=st[region[r2][p2]] &&
						st[region[r1][p1]]>=st[region[r2][p2]];
					};
					while(p2<region[r2].size() && ok(p1, p2)) ++p2, ++ans;
					++p1;
				}
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:93:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     while(p1<region[r1].size() && p2<region[r2].size()) {
      |           ~~^~~~~~~~~~~~~~~~~~
regions.cpp:93:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     while(p1<region[r1].size() && p2<region[r2].size()) {
      |                                   ~~^~~~~~~~~~~~~~~~~~
regions.cpp:98:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |      while(p2<region[r2].size() && ok(p1, p2)) ++p2, ++ans;
      |            ~~^~~~~~~~~~~~~~~~~~
regions.cpp:58:6: warning: unused variable 'sz_big' [-Wunused-variable]
   58 |  int sz_big = bigs.size();
      |      ^~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 10440 KB Output isn't correct
2 Incorrect 6 ms 10440 KB Output isn't correct
3 Incorrect 8 ms 10468 KB Output isn't correct
4 Incorrect 9 ms 10440 KB Output isn't correct
5 Incorrect 13 ms 10440 KB Output isn't correct
6 Incorrect 26 ms 10568 KB Output isn't correct
7 Incorrect 33 ms 10568 KB Output isn't correct
8 Incorrect 38 ms 10568 KB Output isn't correct
9 Incorrect 51 ms 11052 KB Output isn't correct
10 Incorrect 70 ms 10952 KB Output isn't correct
11 Incorrect 95 ms 11212 KB Output isn't correct
12 Incorrect 120 ms 11720 KB Output isn't correct
13 Incorrect 126 ms 11328 KB Output isn't correct
14 Incorrect 144 ms 11764 KB Output isn't correct
15 Incorrect 180 ms 15296 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 680 ms 14676 KB Output isn't correct
2 Incorrect 817 ms 13164 KB Output isn't correct
3 Incorrect 1184 ms 16960 KB Output isn't correct
4 Incorrect 236 ms 11832 KB Output isn't correct
5 Incorrect 300 ms 14144 KB Output isn't correct
6 Incorrect 516 ms 12984 KB Output isn't correct
7 Incorrect 767 ms 13912 KB Output isn't correct
8 Incorrect 741 ms 20416 KB Output isn't correct
9 Incorrect 1276 ms 18428 KB Output isn't correct
10 Incorrect 1353 ms 25444 KB Output isn't correct
11 Incorrect 1745 ms 17464 KB Output isn't correct
12 Incorrect 897 ms 19512 KB Output isn't correct
13 Incorrect 1127 ms 20016 KB Output isn't correct
14 Incorrect 1273 ms 19156 KB Output isn't correct
15 Incorrect 1662 ms 25408 KB Output isn't correct
16 Incorrect 1764 ms 34816 KB Output isn't correct
17 Incorrect 1864 ms 32520 KB Output isn't correct