Submission #747051

#	Time	Username	Problem	Language	Result	Execution time	Memory
747051		AverageAmogusEnjoyer	Regions (IOI09_regions)	C++17	85 / 100	8077 ms	45004 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];
vector<array<int, 2>> time_in_node[R];
indexed_set<int> time_in[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;
}

int main() {
	scanf("%d%d%d", &n, &r, &q);
	int l; scanf("%d", &l); color[l].pb(0);
	for (int i=1, s, e;i<=n-1;i++) {
		scanf("%d%d", &s, &e);
		s--;
		adj[s].pb(i), adj[i].pb(s);
		color[e].pb(i);
	}
	dfs();
	for (int i = 0; i < R; i++) {
		for (int j: color[i]) {
			time_in[i].insert(tin[j]);
			time_in_node[i].pb({tin[j],j});
		}
		sort(all(time_in_node[i]));	
	}
	map<pair<int, int>, int> done;
	while(q--) {
		int i, j; scanf("%d%d", &i, &j);
		int ans = 0;
		if (done.count({i,j})) { ans = done[{i,j}]; }
		else {
			int sz = time_in_node[i].size(), k = 0;
			while(k < sz) {
				int curr_node = time_in_node[i][k][1];
				array<int,2> l = {tout[curr_node],0};
				int curr = time_in[j].order_of_key(tout[curr_node]) - time_in[j].order_of_key(tin[curr_node]);
				assert(curr>=0);
				ans += curr;
				if (curr == 0) {
					k = (upper_bound(all(time_in_node[i]),l) - time_in_node[i].begin());
				}
				else 
					k++;
			}
			done[{i,j}] = ans;
		}	
		printf("%d\n", ans);
		fflush(stdout);
	}
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d%d%d", &n, &r, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  int l; scanf("%d", &l); color[l].pb(0);
      |         ~~~~~^~~~~~~~~~
regions.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d%d", &s, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~
regions.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   int i, j; scanf("%d%d", &i, &j);
      |             ~~~~~^~~~~~~~~~~~~~~~

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