oj.uz

Submission #750913

# Submission time Handle Problem Language Result Execution time Memory
750913 2023-05-30T13:56:48 Z drdilyor Drawing (CEOI22_drawing) C++17
15 / 100
 1500 ms 117776 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>>& pts, 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(pts.empty());
            return;
        }
        if (ch.size() == 1) {
            res[ch[0]] = ix[pts.front()];
            pts.erase(pts.begin());
            dfs(dfs, pts, ch[0], i);
        } else {
            sort(pts.begin(), pts.end(), [](auto& p, auto& q)->bool {
                return (ll)p.second * q.first > (ll) q.second * p.first;
            });
            assert(pts.size() == subs[ch[0]] + subs[ch[1]]);
            vector p1(pts.begin(), pts.begin() + subs[ch[0]]);
            vector p2(pts.begin() + subs[ch[0]], pts.end());
            sort(p1.begin(), p1.end());
            sort(p2.begin(), p2.end());
            res[ch[0]] = ix[p1.front()];
            res[ch[1]] = ix[p2.front()];
            p1.erase(p1.begin());
            p2.erase(p2.begin());
            dfs(dfs, p1, ch[0], i);
            dfs(dfs, p2, ch[1], i);
        }
    };

    sort(pts.begin(), pts.end());
    res[r] = ix[pts.front()];
    pts.erase(pts.begin());
    dfs(dfs, pts, 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;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In instantiation of 'main()::<lambda(auto:24&, std::vector<std::pair<int, int> >&, int, int)> [with auto:24 = main()::<lambda(auto:24&, std::vector<std::pair<int, int> >&, int, int)>]':
Main.cpp:85:20:   required from here
Main.cpp:68:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   68 |             assert(pts.size() == subs[ch[0]] + subs[ch[1]]);

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 36268 KB Output is correct
2 Execution timed out 1563 ms 117776 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1236 KB Output is correct
2 Correct 143 ms 8496 KB Output is correct
3 Correct 339 ms 23392 KB Output is correct
4 Correct 13 ms 1748 KB Output is correct
5 Correct 22 ms 2436 KB Output is correct
6 Correct 18 ms 1176 KB Output is correct
7 Correct 11 ms 1236 KB Output is correct
8 Correct 15 ms 1220 KB Output is correct
9 Correct 252 ms 17152 KB Output is correct
10 Correct 216 ms 10828 KB Output is correct
11 Correct 13 ms 1748 KB Output is correct
12 Correct 16 ms 1672 KB Output is correct
13 Correct 17 ms 1172 KB Output is correct
14 Correct 16 ms 1272 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1236 KB Output is correct
2 Correct 143 ms 8496 KB Output is correct
3 Correct 339 ms 23392 KB Output is correct
4 Correct 13 ms 1748 KB Output is correct
5 Correct 22 ms 2436 KB Output is correct
6 Correct 18 ms 1176 KB Output is correct
7 Correct 11 ms 1236 KB Output is correct
8 Correct 15 ms 1220 KB Output is correct
9 Correct 252 ms 17152 KB Output is correct
10 Correct 216 ms 10828 KB Output is correct
11 Correct 13 ms 1748 KB Output is correct
12 Correct 16 ms 1672 KB Output is correct
13 Correct 17 ms 1172 KB Output is correct
14 Correct 16 ms 1272 KB Output is correct
15 Correct 35 ms 2992 KB Output is correct
16 Correct 1263 ms 79628 KB Output is correct
17 Correct 1457 ms 57064 KB Output is correct
18 Correct 55 ms 4104 KB Output is correct
19 Correct 85 ms 6424 KB Output is correct
20 Correct 48 ms 2764 KB Output is correct
21 Correct 36 ms 3064 KB Output is correct
22 Correct 47 ms 3256 KB Output is correct
23 Correct 737 ms 27804 KB Output is correct
24 Execution timed out 1573 ms 73872 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1236 KB Output is correct
2 Correct 143 ms 8496 KB Output is correct
3 Correct 339 ms 23392 KB Output is correct
4 Correct 13 ms 1748 KB Output is correct
5 Correct 22 ms 2436 KB Output is correct
6 Correct 18 ms 1176 KB Output is correct
7 Correct 11 ms 1236 KB Output is correct
8 Correct 15 ms 1220 KB Output is correct
9 Correct 252 ms 17152 KB Output is correct
10 Correct 216 ms 10828 KB Output is correct
11 Correct 13 ms 1748 KB Output is correct
12 Correct 16 ms 1672 KB Output is correct
13 Correct 17 ms 1172 KB Output is correct
14 Correct 16 ms 1272 KB Output is correct
15 Correct 35 ms 2992 KB Output is correct
16 Correct 1263 ms 79628 KB Output is correct
17 Correct 1457 ms 57064 KB Output is correct
18 Correct 55 ms 4104 KB Output is correct
19 Correct 85 ms 6424 KB Output is correct
20 Correct 48 ms 2764 KB Output is correct
21 Correct 36 ms 3064 KB Output is correct
22 Correct 47 ms 3256 KB Output is correct
23 Correct 737 ms 27804 KB Output is correct
24 Execution timed out 1573 ms 73872 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 36268 KB Output is correct
2 Execution timed out 1563 ms 117776 KB Time limit exceeded
3 Halted 0 ms 0 KB -