oj.uz

Submission #317425

# Submission time Handle Problem Language Result Execution time Memory
317425 2020-10-29T17:26:05 Z Falcon Regions (IOI09_regions) C++17
55 / 100
 4602 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{800};

int N, R, Q;
vector<vector<int>> child;
vector<int> out, region_of, tour;
vector<vector<int>> precalc_big, region_nodes;


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

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:109:2: note: in expansion of macro 'debug'
  109 |  debug(precalc_big);
      |  ^~~~~
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(tour);
      |  ^~~~~
regions.cpp:26:29: warning: statement has no effect [-Wunused-value]
   26 | #define debug(x...)         42
      |                             ^~
regions.cpp:111:2: note: in expansion of macro 'debug'
  111 |  debug(region_nodes);
      |  ^~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 17 ms 384 KB Output is correct
7 Correct 30 ms 384 KB Output is correct
8 Correct 36 ms 512 KB Output is correct
9 Correct 49 ms 1024 KB Output is correct
10 Correct 94 ms 1152 KB Output is correct
11 Correct 132 ms 1408 KB Output is correct
12 Correct 170 ms 2048 KB Output is correct
13 Correct 193 ms 1784 KB Output is correct
14 Correct 288 ms 2552 KB Output is correct
15 Correct 303 ms 5752 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 209 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 214 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 305 ms 2812 KB Output is correct
5 Correct 408 ms 4856 KB Output is correct
6 Correct 1509 ms 4472 KB Output is correct
7 Correct 1860 ms 5880 KB Output is correct
8 Correct 1447 ms 12408 KB Output is correct
9 Correct 2545 ms 13048 KB Output is correct
10 Correct 4602 ms 19960 KB Output is correct
11 Correct 4420 ms 14072 KB Output is correct
12 Runtime error 376 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 356 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 384 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 364 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 363 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 355 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)