# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1033312 |
2024-07-24T16:23:05 Z |
s_tree |
Regions (IOI09_regions) |
C++17 |
|
2953 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define vt vector
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class T> bool chmin(T& a, const T& b) {
return b<a?a=b, 1:0;
}
template<class T> bool chmax(T& a, const T& b) {
return a<b?a=b, 1:0;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
const int B = 200;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n, r, q;
cin >> n >> r >> q;
vt<vt<int>> g(n+1);
vt<vt<int>> col(r+1);
vt<int> c(n+1);
vt<vt<ll>> precomp(r+1);
for(int i = 1;i<=n;i++) {
if(i>1) {
int par;
cin >> par;
g[par].pb(i);
}
int h;
cin >> h;
c[i] = h;
col[h].pb(i);
}
vt<int> tin(n+1), tout(n+1);
int timer=0;
vt<vt<int>> tinCol(n+1);
vt<vt<int>> toutCol(n+1);
auto dfs = [&](int at, auto &&dfs) -> void {
tin[at]=++timer;
tinCol[c[at]].pb(tin[at]);
for(int to:g[at]) {
dfs(to, dfs);
}
tout[at]=++timer;
toutCol[c[at]].pb(tout[at]);
};
int fixedCol=0;
auto dfs2 = [&](int at, auto &&dfs2) -> int {
int cnt=0;
for(int to:g[at]) {
cnt+=dfs2(to, dfs2);
}
precomp[fixedCol][c[at]]+=cnt;
cnt+=(fixedCol==c[at]);
return cnt;
};
dfs(1, dfs);
for(int i = 1;i<=r;i++) {
if(sz(col[i])>B) {
fixedCol=i;
precomp[i].resize(r+1);
dfs2(1, dfs2);
}
}
while(q--) {
int r1, r2;
cin >> r1 >> r2;
if(sz(col[r2])>B) {
cout << precomp[r2][r1] << endl;
}
else {
ll ans=0;
for(int i:col[r2]) {
ans+=lower_bound(all(tinCol[r1]), tin[i])-tinCol[r1].begin();
ans-=lower_bound(all(toutCol[r1]), tin[i])-toutCol[r1].begin();
}
cout << ans << endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
3 ms |
344 KB |
Output is correct |
5 |
Correct |
4 ms |
344 KB |
Output is correct |
6 |
Correct |
9 ms |
596 KB |
Output is correct |
7 |
Correct |
24 ms |
600 KB |
Output is correct |
8 |
Correct |
25 ms |
600 KB |
Output is correct |
9 |
Correct |
26 ms |
1112 KB |
Output is correct |
10 |
Correct |
52 ms |
1624 KB |
Output is correct |
11 |
Correct |
101 ms |
2460 KB |
Output is correct |
12 |
Correct |
96 ms |
3320 KB |
Output is correct |
13 |
Correct |
144 ms |
3364 KB |
Output is correct |
14 |
Correct |
221 ms |
4412 KB |
Output is correct |
15 |
Correct |
195 ms |
7280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1144 ms |
10760 KB |
Output is correct |
2 |
Correct |
902 ms |
10336 KB |
Output is correct |
3 |
Correct |
2368 ms |
13332 KB |
Output is correct |
4 |
Correct |
185 ms |
4708 KB |
Output is correct |
5 |
Correct |
237 ms |
6560 KB |
Output is correct |
6 |
Correct |
485 ms |
10976 KB |
Output is correct |
7 |
Correct |
1047 ms |
14296 KB |
Output is correct |
8 |
Correct |
830 ms |
24736 KB |
Output is correct |
9 |
Correct |
1711 ms |
34000 KB |
Output is correct |
10 |
Correct |
2183 ms |
98020 KB |
Output is correct |
11 |
Runtime error |
2406 ms |
131072 KB |
Execution killed with signal 9 |
12 |
Correct |
2953 ms |
62808 KB |
Output is correct |
13 |
Correct |
2461 ms |
63556 KB |
Output is correct |
14 |
Correct |
1840 ms |
31088 KB |
Output is correct |
15 |
Correct |
2343 ms |
32088 KB |
Output is correct |
16 |
Runtime error |
1100 ms |
131072 KB |
Execution killed with signal 9 |
17 |
Correct |
2230 ms |
37956 KB |
Output is correct |