제출 #746545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
746545		AverageAmogusEnjoyer	Regions (IOI09_regions)	C++17	0 / 100	94 ms	22692 KiB

regions

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end() 
#define sz(x) (int) x.size()
#define pb push_back
#define ll long long
#define nl '\n'

const int N = 200200, R = 25025;
int n, r, q, timer=0, tin[N], tout[N];
vector<int> adj[N], color[R];
indexed_set<int> b[R];

void dfs(int s=0, int e=-1) {
	tin[s] = timer++;
	for (int node:adj[s]) {
		if (node==e) continue;
		dfs(node,s);
	}
	tout[s] = timer-1;
}

int main() {
	// setIO("");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> r >> q;
	int l; cin >> l; color[l].pb(0);
	for (int i=1, s, e;i<=n-1;i++) {
		cin >> s >> e;
		s--;
		adj[s].pb(i), adj[i].pb(s);
		color[e].pb(i);
	}
	dfs();
	for (int i = 0; i < n; i++)
		cout << tin[i] << " " << tout[i] << nl;
	for (int i = 0; i < R; i++) {
		for (int j: color[i]) {
			b[i].insert(tin[j]);
		}	
	}
	while(q--) {
		int i, j; cin >> i >> j;
		int ans = 0;
		for (int parent:color[i]) {
			int hi = b[j].order_of_key(tout[parent]+1);
			int lo = b[j].order_of_key(tin[parent]);
			ans += (hi - lo);
		}
		cout << ans << endl;
	}
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85