oj.uz

Submission #935653

# Submission time Handle Problem Language Result Execution time Memory
935653 2024-02-29T10:30:38 Z OAleksa Regions (IOI09_regions) C++14
11 / 100
 235 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 2e5 + 69;
const int R = 25069;
const int K = 17;
const int B = 450;
const int M = N * K;
int n, q, r, a[N], cnt[R];
int timer, tin[N], tout[N], up[N][K];
int st1[M], lc1[M], rc1[M];
int root1[N], node1;
map<pair<int, int>, int> was;
map<int, int> c[N];
vector<int> g[N], clr[R];
vector<int> b;
void modify(int v, int v1, int tl, int tr, int pos) {
	if (tl == tr)
		st1[v] = st1[v1] + 1;
	else {
		int mid = (tl + tr) / 2;
		if (pos <= mid) {
			lc1[v] = ++node1;
			rc1[v] = rc1[v1];
			modify(lc1[v], lc1[v1], tl, mid, pos);
		}
		else {
			rc1[v] = ++node1;
			lc1[v] = lc1[v1];
			modify(rc1[v], rc1[v1], mid + 1, tr, pos);
		}
		st1[v] = st1[lc1[v]] + st1[rc1[v]];
	}
}

int get(int v, int v1, int tl, int tr, int pos) {
	if (tl == tr)
		return st1[v1] - st1[v];
	else {
		int mid = (tl + tr) / 2;
		if (pos <= mid)
			return get(lc1[v], lc1[v1], tl, mid, pos);
		else
			return get(rc1[v], rc1[v1], mid + 1, tr, pos);
	}
}

bool anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
	if (anc(a, b))
		return a;
	else if (anc(b, a))
		return b;
	for (int i = K - 1;i >= 0;i--) {
		if (!anc(up[a][i], b) && up[a][i] > 0)	
			a = up[a][i];
	}
	return up[a][0];
}
void dfs(int v, int p) {
	tin[v] = ++timer;
	b.push_back(v);
	up[v][0] = p;
	for (int i = 1;i < K;i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	c[v][a[v]]++;
	for (auto u : g[v]) {
		if (u == p)
			continue;
		c[u] = c[v];
		dfs(u, v);
	}
	tout[v] = timer;
	c[v][a[v]]--;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n >> r >> q;
  	cin >> a[1];
  	clr[a[1]].push_back(1);
  	for (int i = 2;i <= n;i++) {
  		int x;
  		cin >> x >> a[i];
  		g[x].push_back(i);
  		g[i].push_back(x);
  		cnt[a[i]]++;
  		clr[a[i]].push_back(i);
  	}
  	dfs(1, 0);
  	for (int i = 1;i <= n;i++) {
  		root1[i] = ++node1;
  		modify(root1[i], root1[i - 1], 1, n, a[b[i - 1]]);
  	}
  	for (int i = 1;i <= r;i++) 
			sort(clr[i].begin(), clr[i].end());
  	while (q--) {
  		int r1, r2;
  		cin >> r1 >> r2;
  		int ans = 0;
  		if (was.count({r1, r2}))
  			ans = was[{r1, r2}];
  		else if (cnt[r1] > B && cnt[r2] > B) {
  			//nadji lca i samo dfs
  			if (!clr[r1].empty()) {
  				int lc = clr[r1].front();
  				for (int i = 1;i < (int)clr[r1].size();i++)
  					lc = lca(lc, clr[r1][i]);
  				function<void(int, int, int, int, int)> dfs = [&](int v, int p, int r1, int r2, int c) {
  					if (a[v] == r2)
  						ans += c;
  					for (auto u : g[v]) {
  						if (u == p)
  							continue;
  						dfs(u, v, r1, r2, c + (a[v] == r1));
  					}
  				};
  				dfs(lc, up[lc][0], r1, r2, 0);
  			}
  		}
  		else if (cnt[r1] <= B) {
  			for (auto i : clr[r1]) 
  				ans += get(root1[tin[i] - 1], root1[tout[i]], 1, n, r2);
  		}
  		else {
  			for (auto i : clr[r2]) {
  				if (c[i].count(r1))	
  					ans += c[i][r1];
  			}
  		}
  		//nsqrtnlogn
  		cout << ans << endl;
  		if (!was.count({r1, r2}))
  			was[{r1, r2}] = ans;
  	}
  }
  return 0;
}

Subtask #1
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23128 KB Output is correct
2 Correct 5 ms 23128 KB Output is correct
3 Correct 6 ms 23232 KB Output is correct
4 Correct 8 ms 23552 KB Output is correct
5 Correct 9 ms 24508 KB Output is correct
6 Correct 27 ms 30680 KB Output is correct
7 Correct 23 ms 27648 KB Output is correct
8 Correct 37 ms 32948 KB Output is correct
9 Correct 114 ms 96184 KB Output is correct
10 Correct 126 ms 74404 KB Output is correct
11 Runtime error 101 ms 131072 KB Execution killed with signal 9
12 Runtime error 98 ms 131072 KB Execution killed with signal 9
13 Correct 235 ms 68704 KB Output is correct
14 Runtime error 108 ms 131072 KB Execution killed with signal 9
15 Runtime error 130 ms 131072 KB Execution killed with signal 9

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 118 ms 131072 KB Execution killed with signal 9
2 Runtime error 107 ms 131072 KB Execution killed with signal 9
3 Runtime error 111 ms 131072 KB Execution killed with signal 9
4 Runtime error 104 ms 131072 KB Execution killed with signal 9
5 Runtime error 108 ms 131072 KB Execution killed with signal 9
6 Runtime error 104 ms 131072 KB Execution killed with signal 9
7 Runtime error 106 ms 131072 KB Execution killed with signal 9
8 Runtime error 121 ms 131072 KB Execution killed with signal 9
9 Runtime error 127 ms 131072 KB Execution killed with signal 9
10 Runtime error 140 ms 131072 KB Execution killed with signal 9
11 Runtime error 143 ms 131072 KB Execution killed with signal 9
12 Runtime error 127 ms 131072 KB Execution killed with signal 9
13 Runtime error 135 ms 131072 KB Execution killed with signal 9
14 Runtime error 145 ms 131072 KB Execution killed with signal 9
15 Runtime error 135 ms 131072 KB Execution killed with signal 9
16 Runtime error 137 ms 131072 KB Execution killed with signal 9
17 Runtime error 136 ms 131072 KB Execution killed with signal 9