oj.uz

Submission #558817

# Submission time Handle Problem Language Result Execution time Memory
558817 2022-05-08T12:59:03 Z heavylightdecomp Regions (IOI09_regions) C++14
55 / 100
 2244 ms 117028 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN = 2e5+5, mxR = 25005;
int reg[mxN], place[mxN], timer, st[mxN], en[mxN], pref[mxN];
vector<int> tr[mxN], inr[mxN], cans[mxN], pans[mxN], vis[mxN];
vector<pair<int,int>> rev[mxN];
vector<pair<int,int>> all;
const int bsz = 1024;
void euler(int x, int p) {
	st[x] = ++timer;
	place[timer] = reg[x];
	for(auto it : tr[x]) if(it != p) euler(it, x);
	en[x] = timer;
}
signed main() {
	//freopen("regions.in", "r", stdin);
	//freopen("regions.out", "w", stdout);
	int N, R, Q; cin >> N >> R >> Q;
	cin >> reg[1];
	inr[reg[1]].push_back(1);

	for(int i = 2; i <= N; i++) {
		int s, h; cin >> s >> h;
		reg[i] = h;
		tr[s].push_back(i);
		tr[i].push_back(s);
		inr[h].push_back(i);
	}
	euler(1, -1);
	for(int i = 1; i <= N; i++) all.push_back({st[i], i});
	sort(all.begin(), all.end());
	for(int r = 1; r <= R; r++) {
		for(auto it : inr[r]) rev[r].push_back({st[it], 0}), rev[r].push_back({en[it]+1, 1}), vis[r].push_back(st[it]);
		sort(rev[r].begin(), rev[r].end());
		sort(vis[r].begin(), vis[r].end());
	}

	for(int r = 1; r <= R; r++) {
		if(inr[r].size() > bsz) {
			cans[r] = pans[r] = vector<int> (mxR);
			for(int i = 0; i < mxN; i++) pref[i] = 0;
			for(auto bad : vis[r]) pref[bad]++;
			for(int i = 1; i < mxN; i++) pref[i] += pref[i-1];
			#define get(l,r) (pref[(r)]-(((l)>0)?pref[(l)-1]:0))
			for(int k = 1; k <= R; k++) {
				if(k==r) continue;
				for(auto member : inr[k]) cans[r][k] += get(st[member], en[member]);
			}
			int j = 0;
			int active = 0;
			for(int c = 1; c <= N; c++) {
				while(j < int(rev[r].size()) && rev[r][j].first <= c) {
					if(rev[r][j].second) active--; else active++;
					j++;
				} 
				pans[r][place[c]] += active;
			}
		}
	}

	for(int g = 1; g <= Q; g++) {
		int a, b; cin >> a >> b;
		if(inr[reg[a]].size() > bsz) {
			cout << pans[a][b] << endl;
		} else if(inr[reg[b]].size() > bsz) {
			cout << cans[b][a] << endl;
		} else {
			int j = 0, active = 0,  res = 0;
			for(int ct : vis[b]) {
				while(j < int(rev[a].size()) && rev[a][j].first <= ct) {
					if(rev[a][j].second) active--; else active++;
					j++;
				}
				res += active;
			}
			cout << res << endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28496 KB Output is correct
2 Correct 15 ms 28420 KB Output is correct
3 Correct 16 ms 28468 KB Output is correct
4 Correct 18 ms 28492 KB Output is correct
5 Correct 21 ms 28424 KB Output is correct
6 Correct 33 ms 28564 KB Output is correct
7 Correct 41 ms 28620 KB Output is correct
8 Correct 48 ms 28624 KB Output is correct
9 Correct 58 ms 29136 KB Output is correct
10 Correct 93 ms 29392 KB Output is correct
11 Correct 120 ms 29876 KB Output is correct
12 Correct 133 ms 30420 KB Output is correct
13 Correct 155 ms 30760 KB Output is correct
14 Correct 191 ms 31556 KB Output is correct
15 Correct 226 ms 34168 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 74916 KB Execution killed with signal 11
2 Runtime error 120 ms 76668 KB Execution killed with signal 11
3 Runtime error 128 ms 81980 KB Execution killed with signal 11
4 Correct 237 ms 31420 KB Output is correct
5 Correct 350 ms 32964 KB Output is correct
6 Correct 716 ms 33212 KB Output is correct
7 Correct 877 ms 35140 KB Output is correct
8 Correct 763 ms 40528 KB Output is correct
9 Correct 1495 ms 43828 KB Output is correct
10 Correct 1905 ms 48436 KB Output is correct
11 Correct 2244 ms 47412 KB Output is correct
12 Runtime error 264 ms 93920 KB Execution killed with signal 11
13 Runtime error 236 ms 95336 KB Execution killed with signal 11
14 Runtime error 277 ms 101116 KB Execution killed with signal 11
15 Runtime error 249 ms 103656 KB Execution killed with signal 11
16 Runtime error 231 ms 113336 KB Execution killed with signal 11
17 Runtime error 269 ms 117028 KB Execution killed with signal 11