/* IOI 2009 "region" problem.
*
* Solution by Bruce Merry.
*
* This is the second solution described in the writeup. Briefly:
* - queries are cached so that duplicate queries can be answered again quickly
* - each new quality is answered in either O(A log B), O(B log A) or O(A + B),
* whichever is deemed fastest.
*/
#include <bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using IP = pair<int, int>;
using LL = long long;
/* An employee in the tree */
struct Emp {
int id; /* New employee ID from a pre-order walk (0-based) */
int reg; /* Employee's home region */
int low; /* Lowest ID of managees */
int high; /* Highest ID of managees */
VI ch; /* Supervisees */
};
struct Reg {
VI ids; /* Sorted list of (new) employee IDs */
/* Sorted of intervals with the same nesting level. Each pair is
* (ID, depth) where ID is the left end-point of the interval (inclusive).
* The right end-point is implicit from the following interval.
*/
vector<IP> ranges;
int depth; /* Working depth during the DFS. */
Reg() : ids(), ranges(), depth(0) {}
};
int N, R, Q;
vector<Emp> nodes;
vector<Reg> RS;
/* Does a pre-order walk over the subtree rooted at root. id_pool contains
* the next unused employee ID, and on return it will be updated to again
* be the next available ID.
*
* This procedure builds the RS arrays, after which the tree is no
* longer needed.
*/
void dfs(int u, int &timer) {
auto& r = RS[nodes[u].reg];
r.ids.push_back(timer++);
/* Depth changed, so after this point we need a new range */
r.ranges.push_back(make_pair(timer, ++r.depth));
for (int v : nodes[u].ch)
dfs(v, timer);
/* Undo the depth change, and start another interval after the last managee. */
r.ranges.push_back(make_pair(timer, --r.depth));
}
/* Query in O(R2 log R1) time, by counting for each employee in r2. */
LL query_by_id(const Reg &r1, const Reg &r2) {
LL ans = 0;
for (int pos : r2.ids) {
/* Find the first range that starts at pos or later. This will
* actually be the range after the one we want.
*/
auto it = lower_bound(r1.ranges.begin(), r1.ranges.end(), make_pair(pos, INT_MAX));
if (it != r1.ranges.begin())
ans += prev(it)->second;
}
return ans;
}
/* Query in O(R1 log R2) time, by counting for each employee in r1 */
LL query_by_range(const Reg &r1, const Reg &r2) {
LL ans = 0;
for (size_t i = 0; i + 1 < r1.ranges.size(); i++) {
int p1 = r1.ranges[i].first, p2 = r1.ranges[i + 1].first;
/* Each employee from r2 in [p1, p2) has depth managers
* from r1. Find the intersections of [p1, p2) with the
* employee list for r2.
*/
auto first = lower_bound(r2.ids.begin(), r2.ids.end(), p1),
last = lower_bound(r2.ids.begin(), r2.ids.end(), p2);
ans += r1.ranges[i].second * (last - first);
}
return ans;
}
/* Query in O(R1 + R2) time, by counting for each employee in r1
* but with a linear sweep instead of a binary search.
*/
LL query_stitch(const Reg &r1, const Reg &r2) {
LL ans = 0;
/* Find the first employee id that is in the first range */
auto id = r2.ids.begin();
if (r1.ranges.empty()) return ans;
while (id != r2.ids.end() && *id < r1.ranges[0].first) id++;
/* Iterate over the ranges as above */
for (size_t i = 0; i + 1 < r1.ranges.size() && id != r2.ids.end(); i++) {
/* Find the end of the section of employees from this range */
auto id_bak = id;
while (id != r2.ids.end() && *id < r1.ranges[i + 1].first)
id++;
ans += r1.ranges[i].second * (id - id_bak);
}
return ans;
}
LL solve(int r1, int r2) {
map<IP, LL> cache;
IP key(r1, r2);
if (cache.count(key)) return cache[key];
const Reg ®1 = RS[r1], ®2 = RS[r2];
int sz1 = reg1.ids.size(), sz2 = reg2.ids.size();
int costs[3] = {
sz1 * ((int)log2(sz2) + 2) * 5, sz2 * ((int)log2(sz1) + 2) * 5, sz1 + sz2
};
// LL ans = 0;
int k = min_element(costs, costs + 3) - costs;
if(k == 0) return cache[key] = query_by_range(reg1, reg2);
if(k == 1) return cache[key] = query_by_id(reg1, reg2);
return cache[key] = query_stitch(reg1, reg2);
// switch ()
// {
// case 0:
// ans =
// break;
// case 1:
// ans =
// break;
// case 2:
// ans =
// break;
// }
// return cache[key] = ans;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> R >> Q, nodes.resize(N), RS.resize(R);
cin >> nodes[0].reg, --nodes[0].reg;
for (int i = 1, fa; i < N; i++) {
cin >> fa >> nodes[i].reg;
--fa, --nodes[i].reg, nodes[fa].ch.push_back(i);
}
int id_pool = 0;
dfs(0, id_pool);
for (int q = 0, r1, r2; q < Q; q++) {
cin >> r1 >> r2, r1--, r2--;
cout << solve(r1, r2) << endl;
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Output is correct |
| 2 |
Correct |
1 ms |
200 KB |
Output is correct |
| 3 |
Correct |
2 ms |
200 KB |
Output is correct |
| 4 |
Correct |
5 ms |
200 KB |
Output is correct |
| 5 |
Correct |
8 ms |
328 KB |
Output is correct |
| 6 |
Correct |
16 ms |
328 KB |
Output is correct |
| 7 |
Correct |
25 ms |
456 KB |
Output is correct |
| 8 |
Correct |
34 ms |
456 KB |
Output is correct |
| 9 |
Correct |
46 ms |
1096 KB |
Output is correct |
| 10 |
Correct |
71 ms |
1352 KB |
Output is correct |
| 11 |
Correct |
115 ms |
1864 KB |
Output is correct |
| 12 |
Correct |
119 ms |
2692 KB |
Output is correct |
| 13 |
Correct |
138 ms |
2584 KB |
Output is correct |
| 14 |
Correct |
149 ms |
3508 KB |
Output is correct |
| 15 |
Correct |
197 ms |
7016 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2359 ms |
8456 KB |
Output is correct |
| 2 |
Correct |
3920 ms |
7400 KB |
Output is correct |
| 3 |
Correct |
3521 ms |
11196 KB |
Output is correct |
| 4 |
Correct |
265 ms |
3652 KB |
Output is correct |
| 5 |
Correct |
299 ms |
5880 KB |
Output is correct |
| 6 |
Correct |
559 ms |
5848 KB |
Output is correct |
| 7 |
Correct |
842 ms |
7964 KB |
Output is correct |
| 8 |
Correct |
753 ms |
15096 KB |
Output is correct |
| 9 |
Correct |
1273 ms |
18060 KB |
Output is correct |
| 10 |
Correct |
1704 ms |
24360 KB |
Output is correct |
| 11 |
Correct |
1920 ms |
19788 KB |
Output is correct |
| 12 |
Correct |
1022 ms |
19988 KB |
Output is correct |
| 13 |
Correct |
1217 ms |
20536 KB |
Output is correct |
| 14 |
Correct |
1574 ms |
20648 KB |
Output is correct |
| 15 |
Correct |
2005 ms |
26296 KB |
Output is correct |
| 16 |
Correct |
1916 ms |
33184 KB |
Output is correct |
| 17 |
Correct |
2628 ms |
31724 KB |
Output is correct |
