Submission #558818

#	Time	Username	Problem	Language	Result	Execution time	Memory
558818		heavylightdecomp	Regions (IOI09_regions)	C++14	100 / 100	2092 ms	84268 KiB

regions

#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 / 15
• Subtask 2: 85 / 85