oj.uz

Submission #365080

# Submission time Handle Problem Language Result Execution time Memory
365080 2021-02-10T21:10:56 Z crackersamdjam Regions (IOI09_regions) C++17
0 / 100
 104 ms 48384 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif

using namespace std;
const int MM = 2e5+5, SQ = 500;

int n, m, q;
vector<int> adj[MM];
int in[MM], out[MM], t;
map<int, int> cnt[MM], parcnt;
int val[MM];
vector<pair<int, int>> down[MM], up[MM];
vector<int> nodes[MM];
int ans[MM], bit[MM];

void update(int i, int v){
	for(; i < MM; i += i&-i)
		bit[i] += v;
}

int query(int i){
	int v = 0;
	for(; i; i -= i&-i)
		v += bit[i];
	return v;
}

void dfs(int cur, int pre){
	in[cur] = ++t;
	for(auto u: adj[cur]){
		if(u == pre) continue;
		dfs(u, cur);
	}
	out[cur] = t;
}

void go(int cur, int pre){
	parcnt[val[cur]]++;
	for(auto [a, i]: up[cur]){
		ans[i] += parcnt[a];
	}

	int id = 0;
	for(auto u: adj[cur]){
		if(u == pre) continue;
		go(u, cur);
		if(size(cnt[u]) > size(cnt[id]))
			id = u;
	}
	cnt[cur] = move(cnt[id]);
	for(auto u: adj[cur]){
		if(u == pre) continue;
		if(u != id){
			for(auto [a, c]: cnt[u]){
				cnt[cur][a] += c;
			}
		}
	}
	cnt[cur][val[cur]]++;
	for(auto [a, i]: down[cur]){
		ans[i] += cnt[cur][a];
	}

	parcnt[val[cur]]--;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>q;
	cin>>val[1];
	nodes[val[1]].emplace_back(1);
	for(int i = 2,p; i <= n; i++){
		cin>>p>>val[i];
		// pr(p, i, val[i]);
		adj[p].emplace_back(i);
		nodes[val[i]].emplace_back(i);
	}
	dfs(1, 0);
	for(int i = 0,a,b; i < q; i++){
		cin>>a>>b;
		// if(size(nodes[a]) > SQ){
		// 	for(int j: nodes[b])
		// 		up[j].emplace_back(a, i);
		// }
		// else if(size(nodes[b]) > SQ){
		// 	for(int j: nodes[a])
		// 		down[j].emplace_back(b, i);
		// }
		// else
		{
			for(int j: nodes[b]){
				update(in[j], 1);
			}
			for(int j: nodes[a]){
				ans[i] += query(out[j]) - query(in[j]-1);
			}
			for(int j: nodes[b]){
				update(in[j], -1);
			}
		}
	}
	// go(1, 0);
	for(int i = 0; i < q; i++)
		cout<<ans[i]<<'\n';
}
/*
for pairs < sqrt, update and query on ett O(n log n)

dfs small to large
O(n log n) for inserting
to query, use small to query for large
O(small*large)
O(n sqrt n)

large to large
O(sqrtn sqrtn) = O(n)

so during dfs, I need one map to store the set of parents and another for subtree (this needs small to large)

*/

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 17 ms 28652 KB Time limit exceeded (wall clock)
2 Execution timed out 20 ms 28524 KB Time limit exceeded (wall clock)
3 Execution timed out 17 ms 28524 KB Time limit exceeded (wall clock)
4 Execution timed out 19 ms 28524 KB Time limit exceeded (wall clock)
5 Execution timed out 17 ms 28652 KB Time limit exceeded (wall clock)
6 Execution timed out 19 ms 28652 KB Time limit exceeded (wall clock)
7 Execution timed out 17 ms 28652 KB Time limit exceeded (wall clock)
8 Execution timed out 18 ms 28780 KB Time limit exceeded (wall clock)
9 Execution timed out 18 ms 29164 KB Time limit exceeded (wall clock)
10 Execution timed out 20 ms 29036 KB Time limit exceeded (wall clock)
11 Execution timed out 21 ms 29292 KB Time limit exceeded (wall clock)
12 Execution timed out 22 ms 29804 KB Time limit exceeded (wall clock)
13 Execution timed out 24 ms 29420 KB Time limit exceeded (wall clock)
14 Execution timed out 26 ms 30060 KB Time limit exceeded (wall clock)
15 Execution timed out 28 ms 32620 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 38 ms 33004 KB Time limit exceeded (wall clock)
2 Execution timed out 47 ms 31852 KB Time limit exceeded (wall clock)
3 Execution timed out 49 ms 34796 KB Time limit exceeded (wall clock)
4 Execution timed out 26 ms 30060 KB Time limit exceeded (wall clock)
5 Execution timed out 27 ms 31588 KB Time limit exceeded (wall clock)
6 Execution timed out 34 ms 31340 KB Time limit exceeded (wall clock)
7 Execution timed out 41 ms 31980 KB Time limit exceeded (wall clock)
8 Execution timed out 49 ms 37228 KB Time limit exceeded (wall clock)
9 Execution timed out 75 ms 36972 KB Time limit exceeded (wall clock)
10 Execution timed out 73 ms 42092 KB Time limit exceeded (wall clock)
11 Execution timed out 89 ms 36844 KB Time limit exceeded (wall clock)
12 Execution timed out 96 ms 38764 KB Time limit exceeded (wall clock)
13 Execution timed out 88 ms 38892 KB Time limit exceeded (wall clock)
14 Execution timed out 104 ms 38380 KB Time limit exceeded (wall clock)
15 Execution timed out 91 ms 42716 KB Time limit exceeded (wall clock)
16 Execution timed out 99 ms 48384 KB Time limit exceeded (wall clock)
17 Execution timed out 87 ms 46956 KB Time limit exceeded (wall clock)