Submission #317427

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
317427	2020-10-29T17:30:51 Z	Falcon	Regions (IOI09_regions)	C++17	55 / 100	4672 ms	131076 KB

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{800};
constexpr int MAXN{200'000};
constexpr int MAXR{25'000};


int N, R, Q;
vector<int> child[MAXN];
int out[MAXN], region_of[MAXN];
vector<int> tour;
vector<int> precalc_big[MAXR], region_nodes[MAXR];


void dfs(int u) {
	static int t{};
	int in = t++;
	region_nodes[region_of[u]].pb(in);
	tour.pb(u);
	for(auto v : child[u]) dfs(v);
	out[in] = t;
}

void solve_big(int r) {
	vector<int>& nodes = region_nodes[r];
	precalc_big[r].resize(R);
	
	sort(all(nodes));
	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() && *next_node == i) 
			current_nodes.push(*next_node);
		precalc_big[r][region_of[tour[i]]] += current_nodes.size();
	}
}

int solve_small(int r1, int r2) {
	int ans{};
	for(auto node : region_nodes[r1])
		ans += lower_bound(all(region_nodes[r2]), out[node]) - lower_bound(all(region_nodes[r2]), node);
	return ans;
}

int main() {

#ifdef DEBUG
	freopen("debug", "w", stderr);
#endif
	
	cin >> N >> R >> Q;

	//child.resize(N); out.resize(N); 
	//tour.reserve(N); region_of.resize(N);
	//precalc_big.resize(R); region_nodes.resize(R);

	rep(i, N) {
		if(i) {
			int p; cin >> p; --p;
			child[p].pb(i);
		}
		cin >> region_of[i]; --region_of[i];
	}

	dfs(0);

	rep(r, R)
		if(region_nodes[r].size() >= BLOCK)
			solve_big(r);

	vi().swap(tour);

	//debug(precalc_big);
	//debug(tour);
	//debug(region_nodes);

	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;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6144 KB	Output is correct
2	Correct	5 ms	6144 KB	Output is correct
3	Correct	6 ms	6144 KB	Output is correct
4	Correct	9 ms	6144 KB	Output is correct
5	Correct	13 ms	6216 KB	Output is correct
6	Correct	22 ms	6272 KB	Output is correct
7	Correct	32 ms	6272 KB	Output is correct
8	Correct	43 ms	6272 KB	Output is correct
9	Correct	53 ms	6784 KB	Output is correct
10	Correct	95 ms	6656 KB	Output is correct
11	Correct	141 ms	6912 KB	Output is correct
12	Correct	166 ms	7552 KB	Output is correct
13	Correct	202 ms	7040 KB	Output is correct
14	Correct	304 ms	7544 KB	Output is correct
15	Correct	293 ms	10740 KB	Output is correct

Subtask #2

40.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	200 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Runtime error	206 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	218 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Correct	308 ms	7672 KB	Output is correct
5	Correct	399 ms	9720 KB	Output is correct
6	Correct	1513 ms	8820 KB	Output is correct
7	Correct	1846 ms	9872 KB	Output is correct
8	Correct	1374 ms	15476 KB	Output is correct
9	Correct	2377 ms	14832 KB	Output is correct
10	Correct	4672 ms	20588 KB	Output is correct
11	Correct	4274 ms	13932 KB	Output is correct
12	Runtime error	378 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	356 ms	131072 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	388 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Runtime error	362 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Runtime error	367 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	365 ms	131076 KB	Execution killed with signal 9 (could be triggered by violating memory limits)