Submission #317432

#	Time	Username	Problem	Language	Result	Execution time	Memory
317432		Falcon	Regions (IOI09_regions)	C++17	100 / 100	5245 ms	29112 KiB

regions

#pragma GCC optimize("O2")
 
#include <bits/stdc++.h>
 
#ifdef DEBUG
#include "debug.hpp"
#endif
 
using namespace std;
 
#define all(c)              (c).begin(), (c).end()
#define rall(c)             (c).rbegin(), (c).rend()
#define traverse(c, it)     for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N)           for(int i = 0; i < (N); ++i)
#define rrep(i, N)          for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N)          for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e)       for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d)    for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back
 
 
#ifdef DEBUG
#define debug(x...)         { ++dbg::depth; string dbg_vals = dbg::to_string(x); --dbg::depth; dbg::fprint(__func__, __LINE__, #x, dbg_vals); }
#define light_debug(x)      { dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0; }
#else
#define debug(x...)         42
#define light_debug(x)      42
#endif
 
 
template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
 
template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }
 
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
 
constexpr int BLOCK{512};
 
int N, R, Q;
vector<vector<int>> child;
vector<int> in, out, region_of, par, tour;
vector<vector<int>> precalc_big, region_in, region_nodes;
 
 
void dfs(int u) {
	static int t{};
	in[u] = t++;
	region_in[region_of[u]].pb(in[u]);
	region_nodes[region_of[u]].pb(u);
	tour.pb(u);
	for(auto v : child[u]) dfs(v);
	out[u] = t;
}
 
void solve_big(int r) {
	vector<int>& nodes = region_nodes[r];
	vector<int> result(R);
	
	sort(all(nodes), [&](int i, int j) { return in[i] < in[j]; });
	stack<int> current_nodes;
	auto next_node = nodes.begin();
	rep(i, N) {
		while(!current_nodes.empty() && out[current_nodes.top()] == i) 
			current_nodes.pop();
		while(next_node != nodes.end() && in[*next_node] == i) 
			current_nodes.push(*next_node), ++next_node;
		result[region_of[tour[i]]] += current_nodes.size();
	}
	precalc_big[r] = result;
}
 
int solve_small(int r1, int r2) {
	int ans{};
	for(auto node : region_nodes[r1])
		ans += lower_bound(all(region_in[r2]), out[node]) - lower_bound(all(region_in[r2]), in[node]);
	return ans;
}
 
int main() {
 
#ifdef DEBUG
	freopen("debug", "w", stderr);
#endif
	
	cin >> N >> R >> Q;
 
	child.resize(N); in.resize(N); out.resize(N); 
	par.resize(N); tour.reserve(N); region_of.resize(N);
	precalc_big.resize(R); region_nodes.resize(R), region_in.resize(R);
 
	rep(i, N) {
		if(i) cin >> par[i], child[--par[i]].pb(i);
		else par[i] = -1;
 
		cin >> region_of[i]; --region_of[i];
	}
 
	dfs(0);
 
	rep(r, R)
		if(region_nodes[r].size() >= BLOCK)
			solve_big(r);
 
	debug(precalc_big);
	debug(tour);
	debug(in, out);
 
	rep(_, Q) {
		int r1, r2; cin >> r1 >> r2; --r1, --r2;
		if(region_nodes[r1].size() >= BLOCK)
			cout << precalc_big[r1][r2] << endl;
		else
			cout << solve_small(r1, r2) << endl;
	}
 
 
 
#ifdef DEBUG
	dbg::dout << "\nExecution time: " << clock() << "ms\n";
#endif
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:26:29: warning: statement has no effect [-Wunused-value]
   26 | #define debug(x...)         42
      |                             ^~
regions.cpp:108:2: note: in expansion of macro 'debug'
  108 |  debug(precalc_big);
      |  ^~~~~
regions.cpp:26:29: warning: statement has no effect [-Wunused-value]
   26 | #define debug(x...)         42
      |                             ^~
regions.cpp:109:2: note: in expansion of macro 'debug'
  109 |  debug(tour);
      |  ^~~~~
regions.cpp:26:29: warning: statement has no effect [-Wunused-value]
   26 | #define debug(x...)         42
      |                             ^~
regions.cpp:110:2: note: in expansion of macro 'debug'
  110 |  debug(in, out);
      |  ^~~~~

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