| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 317432 |
2020-10-29T17:44:24 Z |
Falcon |
Regions (IOI09_regions) |
C++17 |
|
5245 ms |
29112 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), ++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);
| ^~~~~
| # |
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 |
7 ms |
384 KB |
Output is correct |
| 5 |
Correct |
9 ms |
384 KB |
Output is correct |
| 6 |
Correct |
20 ms |
384 KB |
Output is correct |
| 7 |
Correct |
36 ms |
512 KB |
Output is correct |
| 8 |
Correct |
34 ms |
512 KB |
Output is correct |
| 9 |
Correct |
56 ms |
1024 KB |
Output is correct |
| 10 |
Correct |
93 ms |
1152 KB |
Output is correct |
| 11 |
Correct |
156 ms |
1664 KB |
Output is correct |
| 12 |
Correct |
159 ms |
2304 KB |
Output is correct |
| 13 |
Correct |
234 ms |
2048 KB |
Output is correct |
| 14 |
Correct |
240 ms |
2808 KB |
Output is correct |
| 15 |
Correct |
327 ms |
5880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1967 ms |
7392 KB |
Output is correct |
| 2 |
Correct |
2191 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
2847 ms |
9704 KB |
Output is correct |
| 4 |
Correct |
260 ms |
3192 KB |
Output is correct |
| 5 |
Correct |
441 ms |
5240 KB |
Output is correct |
| 6 |
Correct |
1654 ms |
5440 KB |
Output is correct |
| 7 |
Correct |
1795 ms |
7320 KB |
Output is correct |
| 8 |
Correct |
1506 ms |
13148 KB |
Output is correct |
| 9 |
Correct |
2787 ms |
15600 KB |
Output is correct |
| 10 |
Correct |
5018 ms |
21840 KB |
Output is correct |
| 11 |
Correct |
5245 ms |
17700 KB |
Output is correct |
| 12 |
Correct |
1704 ms |
18424 KB |
Output is correct |
| 13 |
Correct |
2638 ms |
18488 KB |
Output is correct |
| 14 |
Correct |
3502 ms |
20532 KB |
Output is correct |
| 15 |
Correct |
4537 ms |
23800 KB |
Output is correct |
| 16 |
Correct |
3795 ms |
29100 KB |
Output is correct |
| 17 |
Correct |
3573 ms |
29112 KB |
Output is correct |
