oj.uz

Submission #750918

# Submission time Handle Problem Language Result Execution time Memory
750918 2023-05-30T14:05:22 Z drdilyor Drawing (CEOI22_drawing) C++17
30 / 100
 1500 ms 19120 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9;
const ll infl = 1e18;
mt19937 rng;

using pt = pair<int,int>;
bool ccw(pt A, pt B, pt C) {
    return ll(C.second-A.second) * (B.first-A.first) > ll(B.second-A.second) * (C.first-A.first);
}
bool intersect(pt A, pt B, pt C, pt D) {
    return ccw(A, C, D) != ccw(B, C, D) && ccw(A, B, C) != ccw(A, B, D);
}

int main() {

    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    vector<pair<int,int>> pts(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--;v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    map<pair<int,int>, int> ix;
    for (auto& [x, y] : pts)
        cin >> x >> y;
    for (int i = 0; i < n; i++)
        ix[pts[i]]= i;

    int r = 0;
    for (; r < n; r++)
        if (adj[r].size() < 3) break;

    vector<int> res(n, -1);
    vector<int> subs(n, 1);
    auto dfs_sz = [&](auto& dfs_sz, int i, int p=-1)->void {
        for (int e : adj[i]) if (e != p) {
            dfs_sz(dfs_sz, e, i);
            subs[i] += subs[e];
        }
    };
    dfs_sz(dfs_sz, r);

    auto dfs = [&](auto& dfs, vector<pair<int,int>>::iterator p1, vector<pair<int,int>>::iterator p2, int i, int p =-1)->void {
        vector<int> ch;
        for (int e : adj[i]) {
            if (e != p) ch.push_back(e);
        }
        if (ch.empty()) {
            assert(p1 == p2);
            return;
        }
        if (ch.size() == 1) {
            res[ch[0]] = ix[*--p2];
            dfs(dfs, p1, p2, ch[0], i);
        } else {
            sort(p1, p2, [](const auto& p, const auto& q)->bool {
                return (ll)p.second * q.first > (ll) q.second * p.first;
            });
            assert(p2 - p1 == subs[ch[0]] + subs[ch[1]]);
            auto q1 = p1 + subs[ch[0]];
            auto q2 = p2;
            p2 = q1;
            //sort(p1, p2, greater());
            //sort(q1, q2, greater());
            res[ch[0]] = ix[*--p2];
            res[ch[1]] = ix[*--q2];
            dfs(dfs, p1, p2, ch[0], i);
            dfs(dfs, q1, q2, ch[1], i);
        }
    };

    sort(pts.begin(), pts.end(), greater());
    res[r] = ix[pts.back()];
    pts.pop_back();
    dfs(dfs, pts.begin(), pts.end(), r);

    vector<int> byp(n);
    for (int i = 0; i < n; i++)
        assert(res[i] >= 0),
        byp[res[i]] = i;
    for (int i : byp) {
        cout << i+1 << ' ';
    }
    cout << '\n';

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 16600 KB Output is correct
2 Execution timed out 1568 ms 19120 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 804 KB Output is correct
2 Correct 48 ms 1092 KB Output is correct
3 Correct 115 ms 1156 KB Output is correct
4 Correct 8 ms 1492 KB Output is correct
5 Correct 15 ms 1532 KB Output is correct
6 Correct 10 ms 852 KB Output is correct
7 Correct 9 ms 1032 KB Output is correct
8 Correct 10 ms 864 KB Output is correct
9 Correct 81 ms 1208 KB Output is correct
10 Correct 74 ms 964 KB Output is correct
11 Correct 9 ms 1364 KB Output is correct
12 Correct 13 ms 1236 KB Output is correct
13 Correct 12 ms 784 KB Output is correct
14 Correct 11 ms 1068 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 804 KB Output is correct
2 Correct 48 ms 1092 KB Output is correct
3 Correct 115 ms 1156 KB Output is correct
4 Correct 8 ms 1492 KB Output is correct
5 Correct 15 ms 1532 KB Output is correct
6 Correct 10 ms 852 KB Output is correct
7 Correct 9 ms 1032 KB Output is correct
8 Correct 10 ms 864 KB Output is correct
9 Correct 81 ms 1208 KB Output is correct
10 Correct 74 ms 964 KB Output is correct
11 Correct 9 ms 1364 KB Output is correct
12 Correct 13 ms 1236 KB Output is correct
13 Correct 12 ms 784 KB Output is correct
14 Correct 11 ms 1068 KB Output is correct
15 Correct 30 ms 1640 KB Output is correct
16 Correct 415 ms 2848 KB Output is correct
17 Correct 501 ms 2072 KB Output is correct
18 Correct 20 ms 3412 KB Output is correct
19 Correct 36 ms 3108 KB Output is correct
20 Correct 26 ms 1708 KB Output is correct
21 Correct 33 ms 2132 KB Output is correct
22 Correct 34 ms 1620 KB Output is correct
23 Correct 251 ms 2308 KB Output is correct
24 Correct 513 ms 2120 KB Output is correct
25 Correct 22 ms 3276 KB Output is correct
26 Correct 30 ms 3112 KB Output is correct
27 Correct 27 ms 1620 KB Output is correct
28 Correct 22 ms 2108 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 804 KB Output is correct
2 Correct 48 ms 1092 KB Output is correct
3 Correct 115 ms 1156 KB Output is correct
4 Correct 8 ms 1492 KB Output is correct
5 Correct 15 ms 1532 KB Output is correct
6 Correct 10 ms 852 KB Output is correct
7 Correct 9 ms 1032 KB Output is correct
8 Correct 10 ms 864 KB Output is correct
9 Correct 81 ms 1208 KB Output is correct
10 Correct 74 ms 964 KB Output is correct
11 Correct 9 ms 1364 KB Output is correct
12 Correct 13 ms 1236 KB Output is correct
13 Correct 12 ms 784 KB Output is correct
14 Correct 11 ms 1068 KB Output is correct
15 Correct 30 ms 1640 KB Output is correct
16 Correct 415 ms 2848 KB Output is correct
17 Correct 501 ms 2072 KB Output is correct
18 Correct 20 ms 3412 KB Output is correct
19 Correct 36 ms 3108 KB Output is correct
20 Correct 26 ms 1708 KB Output is correct
21 Correct 33 ms 2132 KB Output is correct
22 Correct 34 ms 1620 KB Output is correct
23 Correct 251 ms 2308 KB Output is correct
24 Correct 513 ms 2120 KB Output is correct
25 Correct 22 ms 3276 KB Output is correct
26 Correct 30 ms 3112 KB Output is correct
27 Correct 27 ms 1620 KB Output is correct
28 Correct 22 ms 2108 KB Output is correct
29 Correct 321 ms 11784 KB Output is correct
30 Execution timed out 1576 ms 13564 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 16600 KB Output is correct
2 Execution timed out 1568 ms 19120 KB Time limit exceeded
3 Halted 0 ms 0 KB -