oj.uz

Submission #750916

# Submission time Handle Problem Language Result Execution time Memory
750916 2023-05-30T14:01:37 Z drdilyor Drawing (CEOI22_drawing) C++17
15 / 100
 1500 ms 18304 KB 
#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, [](auto& p, 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 623 ms 16588 KB Output is correct
2 Execution timed out 1561 ms 18304 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 852 KB Output is correct
2 Correct 127 ms 1112 KB Output is correct
3 Correct 324 ms 1048 KB Output is correct
4 Correct 8 ms 1496 KB Output is correct
5 Correct 18 ms 1348 KB Output is correct
6 Correct 15 ms 804 KB Output is correct
7 Correct 12 ms 996 KB Output is correct
8 Correct 14 ms 832 KB Output is correct
9 Correct 229 ms 1300 KB Output is correct
10 Correct 206 ms 972 KB Output is correct
11 Correct 9 ms 1444 KB Output is correct
12 Correct 14 ms 1144 KB Output is correct
13 Correct 16 ms 852 KB Output is correct
14 Correct 11 ms 980 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 852 KB Output is correct
2 Correct 127 ms 1112 KB Output is correct
3 Correct 324 ms 1048 KB Output is correct
4 Correct 8 ms 1496 KB Output is correct
5 Correct 18 ms 1348 KB Output is correct
6 Correct 15 ms 804 KB Output is correct
7 Correct 12 ms 996 KB Output is correct
8 Correct 14 ms 832 KB Output is correct
9 Correct 229 ms 1300 KB Output is correct
10 Correct 206 ms 972 KB Output is correct
11 Correct 9 ms 1444 KB Output is correct
12 Correct 14 ms 1144 KB Output is correct
13 Correct 16 ms 852 KB Output is correct
14 Correct 11 ms 980 KB Output is correct
15 Correct 48 ms 1700 KB Output is correct
16 Correct 1209 ms 2756 KB Output is correct
17 Correct 1447 ms 2064 KB Output is correct
18 Correct 23 ms 3412 KB Output is correct
19 Correct 60 ms 3144 KB Output is correct
20 Correct 40 ms 1620 KB Output is correct
21 Correct 28 ms 2208 KB Output is correct
22 Correct 48 ms 1604 KB Output is correct
23 Correct 724 ms 2280 KB Output is correct
24 Execution timed out 1533 ms 2124 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 852 KB Output is correct
2 Correct 127 ms 1112 KB Output is correct
3 Correct 324 ms 1048 KB Output is correct
4 Correct 8 ms 1496 KB Output is correct
5 Correct 18 ms 1348 KB Output is correct
6 Correct 15 ms 804 KB Output is correct
7 Correct 12 ms 996 KB Output is correct
8 Correct 14 ms 832 KB Output is correct
9 Correct 229 ms 1300 KB Output is correct
10 Correct 206 ms 972 KB Output is correct
11 Correct 9 ms 1444 KB Output is correct
12 Correct 14 ms 1144 KB Output is correct
13 Correct 16 ms 852 KB Output is correct
14 Correct 11 ms 980 KB Output is correct
15 Correct 48 ms 1700 KB Output is correct
16 Correct 1209 ms 2756 KB Output is correct
17 Correct 1447 ms 2064 KB Output is correct
18 Correct 23 ms 3412 KB Output is correct
19 Correct 60 ms 3144 KB Output is correct
20 Correct 40 ms 1620 KB Output is correct
21 Correct 28 ms 2208 KB Output is correct
22 Correct 48 ms 1604 KB Output is correct
23 Correct 724 ms 2280 KB Output is correct
24 Execution timed out 1533 ms 2124 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 16588 KB Output is correct
2 Execution timed out 1561 ms 18304 KB Time limit exceeded
3 Halted 0 ms 0 KB -