| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 935679 |
2024-02-29T11:13:17 Z |
OAleksa |
Regions (IOI09_regions) |
C++14 |
|
196 ms |
75272 KB |
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 2e5 + 69;
const int R = 25069;
const int K = 17;
const int B = 450;
int n, q, r, a[N], cnt[R];
int timer, tin[N], tout[N], up[N][K];
int st[R * K], lc[R * K], rc[R * K];
int root[N], node;
map<pair<int, int>, int> was;
vector<int> g[N], clr[R];
void modify(int v, int v1, int tl, int tr, int pos) {
if (tl == tr)
st[v] = st[v1] + 1;
else {
int mid = (tl + tr) / 2;
if (pos <= mid) {
lc[v] = ++node;
rc[v] = rc[v1];
modify(lc[v], lc[v1], tl, mid, pos);
}
else {
rc[v] = ++node;
lc[v] = lc[v1];
modify(rc[v], rc[v1], mid + 1, tr, pos);
}
st[v] = st[lc[v]] + st[rc[v]];
}
}
int get(int v, int tl, int tr, int pos) {
if (tl == tr)
return st[v];
else {
int mid = (tl + tr) / 2;
if (pos <= mid)
return get(lc[v], tl, mid, pos);
else
return get(rc[v], mid + 1, tr, pos);
}
}
bool anc(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (anc(a, b))
return a;
else if (anc(b, a))
return b;
for (int i = K - 1;i >= 0;i--) {
if (!anc(up[a][i], b) && up[a][i] > 0)
a = up[a][i];
}
return up[a][0];
}
void dfs(int v, int p) {
tin[v] = ++timer;
up[v][0] = p;
root[v] = ++node;
modify(root[v], root[p], 1, n, a[v]);
for (int i = 1;i < K;i++)
up[v][i] = up[up[v][i - 1]][i - 1];
for (auto u : g[v]) {
if (u == p)
continue;
dfs(u, v);
}
tout[v] = timer;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> r >> q;
cin >> a[1];
clr[a[1]].push_back(1);
for (int i = 2;i <= n;i++) {
int x;
cin >> x >> a[i];
g[x].push_back(i);
g[i].push_back(x);
cnt[a[i]]++;
clr[a[i]].push_back(i);
}
dfs(1, 0);
for (int i = 1;i <= r;i++) {
sort(clr[i].begin(), clr[i].end(), [&](int x, int y) {
return tin[x] < tin[y];
});
}
while (q--) {
int r1, r2;
cin >> r1 >> r2;
int ans = 0;
if (was.count({r1, r2}))
ans = was[{r1, r2}];
else if (cnt[r1] > B && cnt[r2] > B) {
//nadji lca i samo dfs
if (!clr[r1].empty()) {
int lc = clr[r1].front();
for (int i = 1;i < (int)clr[r1].size();i++)
lc = lca(lc, clr[r1][i]);
function<void(int, int, int, int, int)> dfs = [&](int v, int p, int r1, int r2, int c) {
if (a[v] == r2)
ans += c;
for (auto u : g[v]) {
if (u == p)
continue;
dfs(u, v, r1, r2, c + (a[v] == r1));
}
};
dfs(lc, up[lc][0], r1, r2, 0);
}
}
else if (cnt[r1] <= B) {
//binarna
for (auto i : clr[r1]) {
int m = clr[r2].size();
int l = 0, r = m - 1, L = m;
while (l <= r) {
int mid = (l + r) / 2;
if (tin[clr[r2][mid]] > tin[i]) {
L = mid;
r = mid - 1;
}
else
l = mid + 1;
}
l = 0, r = m - 1;
int R = m - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (tin[clr[r2][mid]] <= tout[i]) {
R = mid;
l = mid + 1;
}
else
r = mid - 1;
}
ans += R - L + 1;
}
}
else {
for (auto i : clr[r2])
ans += get(root[i], 1, n, r1);
}
//nsqrtnlogn
cout << ans << endl;
if (!was.count({r1, r2}))
was[{r1, r2}] = ans;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
14936 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
14936 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
15244 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
15252 KB |
Output isn't correct |
| 5 |
Incorrect |
6 ms |
15540 KB |
Output isn't correct |
| 6 |
Correct |
12 ms |
15600 KB |
Output is correct |
| 7 |
Incorrect |
16 ms |
15448 KB |
Output isn't correct |
| 8 |
Incorrect |
21 ms |
16040 KB |
Output isn't correct |
| 9 |
Correct |
32 ms |
16964 KB |
Output is correct |
| 10 |
Incorrect |
52 ms |
16812 KB |
Output isn't correct |
| 11 |
Incorrect |
91 ms |
18300 KB |
Output isn't correct |
| 12 |
Incorrect |
93 ms |
18736 KB |
Output isn't correct |
| 13 |
Incorrect |
135 ms |
21328 KB |
Output isn't correct |
| 14 |
Runtime error |
31 ms |
40528 KB |
Execution killed with signal 11 |
| 15 |
Correct |
196 ms |
24224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
44388 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
53 ms |
48632 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
55 ms |
56456 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
33 ms |
40948 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
38 ms |
43616 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
47 ms |
42656 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
47 ms |
48372 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
49 ms |
47440 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
65 ms |
59848 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
80 ms |
63568 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
81 ms |
54872 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
83 ms |
52772 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
78 ms |
57796 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
80 ms |
53960 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
99 ms |
75272 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
86 ms |
58992 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
96 ms |
62224 KB |
Execution killed with signal 11 |
