oj.uz

Submission #317414

# Submission time Handle Problem Language Result Execution time Memory
317414 2020-10-29T17:16:22 Z Falcon Regions (IOI09_regions) C++17
55 / 100
 5665 ms 131076 KB 
#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);
		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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 9 ms 384 KB Output is correct
6 Correct 25 ms 384 KB Output is correct
7 Correct 30 ms 512 KB Output is correct
8 Correct 35 ms 512 KB Output is correct
9 Correct 47 ms 1024 KB Output is correct
10 Correct 88 ms 1280 KB Output is correct
11 Correct 141 ms 1664 KB Output is correct
12 Correct 168 ms 2304 KB Output is correct
13 Correct 212 ms 2176 KB Output is correct
14 Correct 331 ms 2808 KB Output is correct
15 Correct 347 ms 5752 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 233 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 234 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 241 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 394 ms 3192 KB Output is correct
5 Correct 482 ms 5192 KB Output is correct
6 Correct 1653 ms 5440 KB Output is correct
7 Correct 2040 ms 7336 KB Output is correct
8 Correct 1568 ms 13228 KB Output is correct
9 Correct 2871 ms 15480 KB Output is correct
10 Correct 5468 ms 21752 KB Output is correct
11 Correct 5665 ms 17696 KB Output is correct
12 Runtime error 427 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 389 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 427 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 393 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 392 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 385 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)