oj.uz

Submission #477482

# Submission time Handle Problem Language Result Execution time Memory
477482 2021-10-02T09:22:38 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
0 / 100
 1953 ms 34728 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]] &&
						en[region[r1][p1]]>=en[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 10440 KB Output isn't correct
4 Incorrect 10 ms 10452 KB Output isn't correct
5 Incorrect 15 ms 10440 KB Output isn't correct
6 Incorrect 16 ms 10568 KB Output isn't correct
7 Incorrect 30 ms 10568 KB Output isn't correct
8 Incorrect 38 ms 10568 KB Output isn't correct
9 Incorrect 50 ms 11080 KB Output isn't correct
10 Incorrect 82 ms 10912 KB Output isn't correct
11 Incorrect 107 ms 11208 KB Output isn't correct
12 Incorrect 111 ms 11664 KB Output isn't correct
13 Incorrect 136 ms 11200 KB Output isn't correct
14 Incorrect 198 ms 11712 KB Output isn't correct
15 Incorrect 163 ms 15320 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 715 ms 14684 KB Output isn't correct
2 Incorrect 725 ms 13064 KB Output isn't correct
3 Incorrect 1134 ms 17004 KB Output isn't correct
4 Incorrect 138 ms 11744 KB Output isn't correct
5 Incorrect 324 ms 14080 KB Output isn't correct
6 Incorrect 572 ms 13032 KB Output isn't correct
7 Incorrect 759 ms 13880 KB Output isn't correct
8 Incorrect 910 ms 20396 KB Output isn't correct
9 Incorrect 1315 ms 18484 KB Output isn't correct
10 Incorrect 1529 ms 25552 KB Output isn't correct
11 Incorrect 1705 ms 17528 KB Output isn't correct
12 Incorrect 698 ms 19520 KB Output isn't correct
13 Incorrect 1000 ms 19928 KB Output isn't correct
14 Incorrect 1178 ms 19144 KB Output isn't correct
15 Incorrect 1953 ms 25408 KB Output isn't correct
16 Incorrect 1662 ms 34728 KB Output isn't correct
17 Incorrect 1809 ms 32612 KB Output isn't correct