oj.uz

Submission #975529

# Submission time Handle Problem Language Result Execution time Memory
975529 2024-05-05T12:23:51 Z Circling Drawing (CEOI22_drawing) C++17
100 / 100
 894 ms 43624 KB 
/*The British Royal Family and a small cadre of English Fabian Socialists, in
conjunction with the Rockefellers and the Rothchilds, are engaged in a
conspiracy to greatly reduce the population of the human race in order to head
off a Malthusian catastrophe, a catastrophe that could easily be avoided by
simply building a massive amount of nuclear power plants and a number of massive
superhighways and bridges to connect all of the world's continents. But doing
that would cut into the conspiracy's profits. So the British Royal Family
invented environmentalism and neoliberalism in order to hide the truth. And in
order to further reduce the population, the British Royal Family is also the
world's foremost drug trafficking conspiracy. And it uses its control of the IMF
to push austerity in order to kill as many people in the global south as
possible.
And also Henry Kissinger is a gay KGB agent. */
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;


int n, u, v, root = 1, maxysegtree[800000], unusedsegtree[800000], subtreesize[200001], answer[200001];
pair<pair<int, int>, int> points[200000];
vector<vector<int>> graph;


int compy(int xa, int xb){
    if (xa == -1 || xb == -1) return max(xa, xb);
    if (points[xa].first.second > points[xb].first.second) return xa;
    if (points[xa].first.second < points[xb].first.second) return xb;
    if (points[xa] > points[xb]) return xa;
    return xb;
}


int maxy(int l, int r, int node, int nodel, int noder){
    if (noder <= l || r <= nodel) return -1;
    if (l <= nodel && noder <= r) return maxysegtree[node];
    int nodemid = (nodel + noder) / 2;
    int a = maxy(l, r, 2 * node + 1, nodel, nodemid);
    int b = maxy(l, r, 2 * node + 2, nodemid, noder);
    return compy(a, b);
}


int countunused(int l, int r, int node, int nodel, int noder){
    if (noder <= l || r <= nodel) return 0;
    if (l <= nodel && noder <= r) return unusedsegtree[node];
    int nodemid = (nodel + noder) / 2;
    return countunused(l, r, 2 * node + 1, nodel, nodemid) + countunused(l, r, 2 * node + 2, nodemid, noder);
}


void build(int x, pair<pair<int, int>, int> val, int node, int nodel, int noder){
    if (x < nodel || noder <= x) return;
    if (x == nodel && x == noder - 1){
        maxysegtree[node] = x;
        unusedsegtree[node] = 1;
        return;
    }
    int nodemid = (nodel + noder) / 2;
    build(x, val, 2 * node + 1, nodel, nodemid);
    build(x, val, 2 * node + 2, nodemid, noder);
    unusedsegtree[node] = unusedsegtree[2 * node + 1] + unusedsegtree[2 * node + 2];
    maxysegtree[node] = compy(maxysegtree[2 * node + 1], maxysegtree[2 * node + 2]);
}


void use(int x, int node, int nodel, int noder){
    if (x < nodel || noder <= x) return;
    if (x == nodel && x == noder - 1){
        maxysegtree[node] = -1;
        unusedsegtree[node] = 0;
        return;
    }
    int nodemid = (nodel + noder) / 2;
    use(x, 2 * node + 1, nodel, nodemid);
    use(x, 2 * node + 2, nodemid, noder);
    unusedsegtree[node] = unusedsegtree[2 * node + 1] + unusedsegtree[2 * node + 2];
    maxysegtree[node] = compy(maxysegtree[2 * node + 1], maxysegtree[2 * node + 2]);
}


void stdfs(int node, int prev){
    subtreesize[node] = 1;
    for (int child: graph[node]){
        if (child == prev) continue;
        stdfs(child, node);
        subtreesize[node] += subtreesize[child];
    }
}


void compute(int rootnode, int prevnode, int pointl, int pointr){
    int pointroot = maxy(pointl, pointr, 0, 0, n);
    answer[points[pointroot].second + 1] = rootnode;
    use(pointroot, 0, 0, n);
    int cursor = pointl, minr, maxr, midr;
    for (int child: graph[rootnode]){
        if (child == prevnode) continue;
        minr = cursor + 1;
        maxr = pointr;
        while (minr != maxr){
            midr = (minr + maxr) / 2;
            if (countunused(cursor, midr, 0, 0, n) < subtreesize[child]) minr = midr + 1;
            else maxr = midr;
        }
        compute(child, rootnode, cursor, minr);
        cursor = minr;
    }
}


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> n;
    graph.resize(n + 1);
    for (int i = 1; i < n; i++){
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for (; graph[root].size() == 3; root++);
    for (int i = 0; i < n; i++){
        cin >> points[i].first.first >> points[i].first.second;
        points[i].second = i;
    }
    sort(points, points + n);
    for (int i = 0; i < n; i++) build(i, points[i], 0, 0, n);
    stdfs(root, 0);
    compute(root, 0, 0, n);
    for (int i = 1; i <= n; i++) cout << answer[i] << ' ';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 19316 KB Output is correct
2 Correct 368 ms 24656 KB Output is correct
3 Correct 367 ms 23544 KB Output is correct
4 Correct 339 ms 26468 KB Output is correct
5 Correct 397 ms 26704 KB Output is correct
6 Correct 157 ms 18988 KB Output is correct
7 Correct 314 ms 20052 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4952 KB Output is correct
2 Correct 9 ms 5076 KB Output is correct
3 Correct 8 ms 5080 KB Output is correct
4 Correct 9 ms 5212 KB Output is correct
5 Correct 9 ms 5212 KB Output is correct
6 Correct 5 ms 4956 KB Output is correct
7 Correct 8 ms 4956 KB Output is correct
8 Correct 5 ms 4872 KB Output is correct
9 Correct 9 ms 4956 KB Output is correct
10 Correct 8 ms 5024 KB Output is correct
11 Correct 7 ms 5212 KB Output is correct
12 Correct 9 ms 4952 KB Output is correct
13 Correct 5 ms 4956 KB Output is correct
14 Correct 8 ms 4956 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4952 KB Output is correct
2 Correct 9 ms 5076 KB Output is correct
3 Correct 8 ms 5080 KB Output is correct
4 Correct 9 ms 5212 KB Output is correct
5 Correct 9 ms 5212 KB Output is correct
6 Correct 5 ms 4956 KB Output is correct
7 Correct 8 ms 4956 KB Output is correct
8 Correct 5 ms 4872 KB Output is correct
9 Correct 9 ms 4956 KB Output is correct
10 Correct 8 ms 5024 KB Output is correct
11 Correct 7 ms 5212 KB Output is correct
12 Correct 9 ms 4952 KB Output is correct
13 Correct 5 ms 4956 KB Output is correct
14 Correct 8 ms 4956 KB Output is correct
15 Correct 13 ms 5468 KB Output is correct
16 Correct 23 ms 5976 KB Output is correct
17 Correct 23 ms 5736 KB Output is correct
18 Correct 18 ms 6248 KB Output is correct
19 Correct 25 ms 6044 KB Output is correct
20 Correct 13 ms 5464 KB Output is correct
21 Correct 21 ms 5768 KB Output is correct
22 Correct 13 ms 5468 KB Output is correct
23 Correct 24 ms 5724 KB Output is correct
24 Correct 23 ms 5760 KB Output is correct
25 Correct 18 ms 6236 KB Output is correct
26 Correct 24 ms 6112 KB Output is correct
27 Correct 13 ms 5468 KB Output is correct
28 Correct 20 ms 5720 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4952 KB Output is correct
2 Correct 9 ms 5076 KB Output is correct
3 Correct 8 ms 5080 KB Output is correct
4 Correct 9 ms 5212 KB Output is correct
5 Correct 9 ms 5212 KB Output is correct
6 Correct 5 ms 4956 KB Output is correct
7 Correct 8 ms 4956 KB Output is correct
8 Correct 5 ms 4872 KB Output is correct
9 Correct 9 ms 4956 KB Output is correct
10 Correct 8 ms 5024 KB Output is correct
11 Correct 7 ms 5212 KB Output is correct
12 Correct 9 ms 4952 KB Output is correct
13 Correct 5 ms 4956 KB Output is correct
14 Correct 8 ms 4956 KB Output is correct
15 Correct 13 ms 5468 KB Output is correct
16 Correct 23 ms 5976 KB Output is correct
17 Correct 23 ms 5736 KB Output is correct
18 Correct 18 ms 6248 KB Output is correct
19 Correct 25 ms 6044 KB Output is correct
20 Correct 13 ms 5464 KB Output is correct
21 Correct 21 ms 5768 KB Output is correct
22 Correct 13 ms 5468 KB Output is correct
23 Correct 24 ms 5724 KB Output is correct
24 Correct 23 ms 5760 KB Output is correct
25 Correct 18 ms 6236 KB Output is correct
26 Correct 24 ms 6112 KB Output is correct
27 Correct 13 ms 5468 KB Output is correct
28 Correct 20 ms 5720 KB Output is correct
29 Correct 112 ms 15952 KB Output is correct
30 Correct 249 ms 20032 KB Output is correct
31 Correct 232 ms 18516 KB Output is correct
32 Correct 184 ms 21584 KB Output is correct
33 Correct 280 ms 20324 KB Output is correct
34 Correct 108 ms 15952 KB Output is correct
35 Correct 226 ms 16976 KB Output is correct
36 Correct 95 ms 14928 KB Output is correct
37 Correct 248 ms 18792 KB Output is correct
38 Correct 252 ms 18900 KB Output is correct
39 Correct 195 ms 20492 KB Output is correct
40 Correct 275 ms 19044 KB Output is correct
41 Correct 94 ms 14932 KB Output is correct
42 Correct 208 ms 17212 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 19316 KB Output is correct
2 Correct 368 ms 24656 KB Output is correct
3 Correct 367 ms 23544 KB Output is correct
4 Correct 339 ms 26468 KB Output is correct
5 Correct 397 ms 26704 KB Output is correct
6 Correct 157 ms 18988 KB Output is correct
7 Correct 314 ms 20052 KB Output is correct
8 Correct 5 ms 4952 KB Output is correct
9 Correct 9 ms 5076 KB Output is correct
10 Correct 8 ms 5080 KB Output is correct
11 Correct 9 ms 5212 KB Output is correct
12 Correct 9 ms 5212 KB Output is correct
13 Correct 5 ms 4956 KB Output is correct
14 Correct 8 ms 4956 KB Output is correct
15 Correct 5 ms 4872 KB Output is correct
16 Correct 9 ms 4956 KB Output is correct
17 Correct 8 ms 5024 KB Output is correct
18 Correct 7 ms 5212 KB Output is correct
19 Correct 9 ms 4952 KB Output is correct
20 Correct 5 ms 4956 KB Output is correct
21 Correct 8 ms 4956 KB Output is correct
22 Correct 13 ms 5468 KB Output is correct
23 Correct 23 ms 5976 KB Output is correct
24 Correct 23 ms 5736 KB Output is correct
25 Correct 18 ms 6248 KB Output is correct
26 Correct 25 ms 6044 KB Output is correct
27 Correct 13 ms 5464 KB Output is correct
28 Correct 21 ms 5768 KB Output is correct
29 Correct 13 ms 5468 KB Output is correct
30 Correct 24 ms 5724 KB Output is correct
31 Correct 23 ms 5760 KB Output is correct
32 Correct 18 ms 6236 KB Output is correct
33 Correct 24 ms 6112 KB Output is correct
34 Correct 13 ms 5468 KB Output is correct
35 Correct 20 ms 5720 KB Output is correct
36 Correct 112 ms 15952 KB Output is correct
37 Correct 249 ms 20032 KB Output is correct
38 Correct 232 ms 18516 KB Output is correct
39 Correct 184 ms 21584 KB Output is correct
40 Correct 280 ms 20324 KB Output is correct
41 Correct 108 ms 15952 KB Output is correct
42 Correct 226 ms 16976 KB Output is correct
43 Correct 95 ms 14928 KB Output is correct
44 Correct 248 ms 18792 KB Output is correct
45 Correct 252 ms 18900 KB Output is correct
46 Correct 195 ms 20492 KB Output is correct
47 Correct 275 ms 19044 KB Output is correct
48 Correct 94 ms 14932 KB Output is correct
49 Correct 208 ms 17212 KB Output is correct
50 Correct 185 ms 20360 KB Output is correct
51 Correct 763 ms 37740 KB Output is correct
52 Correct 757 ms 32988 KB Output is correct
53 Correct 736 ms 37856 KB Output is correct
54 Correct 894 ms 43624 KB Output is correct
55 Correct 318 ms 28016 KB Output is correct
56 Correct 638 ms 29780 KB Output is correct
57 Correct 59 ms 12504 KB Output is correct
58 Correct 735 ms 33848 KB Output is correct
59 Correct 687 ms 32968 KB Output is correct
60 Correct 859 ms 42580 KB Output is correct
61 Correct 825 ms 36432 KB Output is correct
62 Correct 59 ms 12492 KB Output is correct
63 Correct 613 ms 29624 KB Output is correct