oj.uz

답안 #477489

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477489 2021-10-02T09:35:52 Z Abrar_Al_Samit Regions (IOI09_regions) C++17
0 / 100
 619 ms 120120 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], regionAll[MX], regionEl[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];
		regionEl[H[v]].push_back(v);
	}
	regionAll[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(regionAll[i].size()>B) {
		bigs.push_back(i);
	}
	int sz_big = bigs.size();
	FenwickTree A;
	for(int all=1; all<=25000; ++all) {
		for(auto it : regionAll[all]) {
			A.add(st[it], 1);
		}
		for(auto b : bigs) {
			if(prep[b].empty()) prep[b].resize(25001);
			for(auto it : regionEl[b]) {
				prep[b][all] = A.sum(st[it], en[it]);
			}
		}
		for(auto it : regionAll[all]) {
			A.add(st[it], -1);
		}
	}
	map <int, FenwickTree> sb;
	for(auto b : bigs) {
		for(auto it : regionAll[b]) {
			sb[b].add(st[it], 1);
		}
	}
	while(Q--) {
		int r1, r2;
		cin >> r1 >> r2;
		int ans = 0;
		if(regionAll[r1].size()>B) {
			ans = prep[r1][r2];
		} else {
			if(regionAll[r2].size()>B) {
				for(auto it : regionEl[r1]) {
					ans += sb[r2].sum(st[it], en[it]);
				}
			} else {
				int p1 = 0, p2 = 0;
				while(p1<regionEl[r1].size() && p2<regionAll[r2].size()) {
					cout << regionEl[r1][p1] << ' ' << regionAll[r2][p2] << endl;
					auto ok = [&] (int p1, int p2) {
						return st[regionEl[r1][p1]]<=st[regionAll[r2][p2]] &&
						en[regionEl[r1][p1]]>=en[regionAll[r2][p2]];
					};
					while(p2<regionAll[r2].size() && !ok(p1, p2)) ++p2;
					while(p2<regionAll[r2].size() && ok(p1, p2)) ++p2, ++ans;
					++p1;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 15176 KB Output isn't correct
2 Incorrect 8 ms 15176 KB Output isn't correct
3 Incorrect 9 ms 15176 KB Output isn't correct
4 Incorrect 9 ms 15176 KB Output isn't correct
5 Runtime error 8 ms 15176 KB Execution killed with signal 13
6 Incorrect 13 ms 15252 KB Output isn't correct
7 Runtime error 12 ms 15268 KB Execution killed with signal 13
8 Runtime error 14 ms 15304 KB Execution killed with signal 13
9 Incorrect 19 ms 15832 KB Output isn't correct
10 Runtime error 24 ms 15796 KB Execution killed with signal 13
11 Runtime error 30 ms 16032 KB Execution killed with signal 13
12 Runtime error 38 ms 16544 KB Execution killed with signal 13
13 Runtime error 45 ms 16228 KB Execution killed with signal 13
14 Runtime error 45 ms 16704 KB Execution killed with signal 13
15 Runtime error 67 ms 20384 KB Execution killed with signal 13

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 123 ms 36660 KB Time limit exceeded (wall clock)
2 Execution timed out 304 ms 29892 KB Time limit exceeded (wall clock)
3 Execution timed out 107 ms 31168 KB Time limit exceeded (wall clock)
4 Execution timed out 51 ms 16820 KB Time limit exceeded (wall clock)
5 Execution timed out 57 ms 19148 KB Time limit exceeded (wall clock)
6 Execution timed out 619 ms 71204 KB Time limit exceeded (wall clock)
7 Execution timed out 521 ms 43116 KB Time limit exceeded (wall clock)
8 Execution timed out 405 ms 114212 KB Time limit exceeded (wall clock)
9 Execution timed out 154 ms 24492 KB Time limit exceeded (wall clock)
10 Execution timed out 534 ms 120120 KB Time limit exceeded (wall clock)
11 Execution timed out 224 ms 23888 KB Time limit exceeded (wall clock)
12 Execution timed out 231 ms 27072 KB Time limit exceeded (wall clock)
13 Execution timed out 201 ms 27692 KB Time limit exceeded (wall clock)
14 Execution timed out 489 ms 44864 KB Time limit exceeded (wall clock)
15 Execution timed out 208 ms 33344 KB Time limit exceeded (wall clock)
16 Execution timed out 223 ms 42740 KB Time limit exceeded (wall clock)
17 Execution timed out 292 ms 59100 KB Time limit exceeded (wall clock)