oj.uz

Submission #558816

# Submission time Handle Problem Language Result Execution time Memory
558816 2022-05-08T12:49:35 Z heavylightdecomp Regions (IOI09_regions) C++14
55 / 100
 2338 ms 131072 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> (mxN);
			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 28488 KB Output is correct
2 Correct 13 ms 28448 KB Output is correct
3 Correct 14 ms 28500 KB Output is correct
4 Correct 18 ms 28496 KB Output is correct
5 Correct 22 ms 28492 KB Output is correct
6 Correct 32 ms 28496 KB Output is correct
7 Correct 31 ms 28624 KB Output is correct
8 Correct 35 ms 28656 KB Output is correct
9 Correct 60 ms 29136 KB Output is correct
10 Correct 96 ms 29404 KB Output is correct
11 Correct 125 ms 29800 KB Output is correct
12 Correct 130 ms 30476 KB Output is correct
13 Correct 175 ms 30672 KB Output is correct
14 Correct 202 ms 31496 KB Output is correct
15 Correct 232 ms 34236 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 83268 KB Execution killed with signal 11
2 Runtime error 146 ms 99004 KB Execution killed with signal 11
3 Runtime error 168 ms 109864 KB Execution killed with signal 11
4 Correct 241 ms 31428 KB Output is correct
5 Correct 335 ms 32944 KB Output is correct
6 Correct 515 ms 33220 KB Output is correct
7 Correct 904 ms 35228 KB Output is correct
8 Correct 901 ms 40524 KB Output is correct
9 Correct 1599 ms 43912 KB Output is correct
10 Correct 2207 ms 48424 KB Output is correct
11 Correct 2338 ms 47324 KB Output is correct
12 Runtime error 256 ms 99352 KB Execution killed with signal 11
13 Runtime error 257 ms 100956 KB Execution killed with signal 11
14 Runtime error 322 ms 131072 KB Execution killed with signal 11
15 Runtime error 254 ms 109212 KB Execution killed with signal 11
16 Runtime error 250 ms 118868 KB Execution killed with signal 11
17 Runtime error 325 ms 131072 KB Execution killed with signal 11