oj.uz

Submission #558818

# Submission time Handle Problem Language Result Execution time Memory
558818 2022-05-08T13:02:11 Z heavylightdecomp Regions (IOI09_regions) C++14
100 / 100
 2092 ms 84268 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
const int mxN = 4e5+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[a].size() > bsz) {
			cout << pans[a][b] << endl;
		} else if(inr[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 27 ms 56552 KB Output is correct
2 Correct 29 ms 56688 KB Output is correct
3 Correct 29 ms 56656 KB Output is correct
4 Correct 32 ms 56684 KB Output is correct
5 Correct 35 ms 56684 KB Output is correct
6 Correct 41 ms 56692 KB Output is correct
7 Correct 50 ms 56728 KB Output is correct
8 Correct 59 ms 56864 KB Output is correct
9 Correct 73 ms 57256 KB Output is correct
10 Correct 99 ms 57544 KB Output is correct
11 Correct 118 ms 57924 KB Output is correct
12 Correct 153 ms 58564 KB Output is correct
13 Correct 170 ms 58832 KB Output is correct
14 Correct 210 ms 59696 KB Output is correct
15 Correct 164 ms 61804 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 65768 KB Output is correct
2 Correct 986 ms 66776 KB Output is correct
3 Correct 1207 ms 69052 KB Output is correct
4 Correct 267 ms 59632 KB Output is correct
5 Correct 354 ms 60736 KB Output is correct
6 Correct 559 ms 61416 KB Output is correct
7 Correct 906 ms 63300 KB Output is correct
8 Correct 879 ms 67712 KB Output is correct
9 Correct 1463 ms 71756 KB Output is correct
10 Correct 2092 ms 75228 KB Output is correct
11 Correct 1966 ms 75572 KB Output is correct
12 Correct 1018 ms 75244 KB Output is correct
13 Correct 1241 ms 75728 KB Output is correct
14 Correct 1460 ms 78800 KB Output is correct
15 Correct 1558 ms 79068 KB Output is correct
16 Correct 2013 ms 82036 KB Output is correct
17 Correct 2047 ms 84268 KB Output is correct