oj.uz

Submission #701089

# Submission time Handle Problem Language Result Execution time Memory
701089 2023-02-20T04:54:52 Z PurpleCrayon Drawing (CEOI22_drawing) C++17
100 / 100
 259 ms 40856 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 2e5+10, MOD = 998244353;

struct P {
    int x, y;
    int id;
    bool dead;

    void read() {
        cin >> x >> y;
    }

    bool operator < (const P& he) const {
        return make_pair(x, y) < make_pair(he.x, he.y);
    }
};

int n, sub[N], ans[N];
vector<int> adj[N];
int nxt[N], prv[N];
P store[N];

int dfs_sub(int c, int p) {
    sub[c] = 1;
    for (int nxt : adj[c]) if (nxt != p)
        sub[c] += dfs_sub(nxt, c);

    return sub[c];
}

int get_sub(int c) {
    return c == -1 ? 0 : sub[c];
}

void dfs(int c, int p, int l, int r) {
    int one = -1, two = -1;
    for (int nxt : adj[c]) if (nxt != p) {
        if (one == -1) one = nxt;
        else two = nxt;
    }

    if (get_sub(one) > get_sub(two)) swap(one, two);

    int m = l;
    for (int i = 0; i < get_sub(one); i++) {
        m = nxt[m];
    }

    ans[m] = c;

    if (two == -1) return;
    if (one == -1) {
        dfs(two, c, nxt[m], r);
    } else {
        dfs(one, c, l, prv[m]);
        dfs(two, c, nxt[m], r);
    }
}

void solve() {
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b, --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }

    int root = -1;
    for (int i = 0; i < n; i++) if (sz(adj[i]) == 1)
        root = i;

    dfs_sub(root, -1);

    vector<P> pts(n); 
    for (int i = 0; i < n; i++) {
        pts[i].read();
        pts[i].id = i, pts[i].dead = 0;
        store[i] = pts[i];
    }

    sort(pts.begin(), pts.end());

    memset(prv, -1, sizeof(prv));
    memset(nxt, -1, sizeof(nxt));
    for (int i = 1; i < n; i++) {
        prv[pts[i].id] = pts[i-1].id;
        nxt[pts[i-1].id] = pts[i].id;
    }

    dfs(root, -1, pts[0].id, pts[n-1].id);

    for (int i = 0; i < n; i++)
        cout << ans[i]+1 << ' ';
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 15400 KB Output is correct
2 Correct 110 ms 18244 KB Output is correct
3 Correct 105 ms 21436 KB Output is correct
4 Correct 135 ms 27808 KB Output is correct
5 Correct 103 ms 23500 KB Output is correct
6 Correct 126 ms 18820 KB Output is correct
7 Correct 120 ms 19888 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6868 KB Output is correct
2 Correct 6 ms 6996 KB Output is correct
3 Correct 6 ms 6996 KB Output is correct
4 Correct 7 ms 7124 KB Output is correct
5 Correct 6 ms 7124 KB Output is correct
6 Correct 5 ms 6800 KB Output is correct
7 Correct 6 ms 6868 KB Output is correct
8 Correct 6 ms 6792 KB Output is correct
9 Correct 6 ms 6996 KB Output is correct
10 Correct 6 ms 6996 KB Output is correct
11 Correct 7 ms 7048 KB Output is correct
12 Correct 6 ms 6996 KB Output is correct
13 Correct 6 ms 6800 KB Output is correct
14 Correct 6 ms 6868 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6868 KB Output is correct
2 Correct 6 ms 6996 KB Output is correct
3 Correct 6 ms 6996 KB Output is correct
4 Correct 7 ms 7124 KB Output is correct
5 Correct 6 ms 7124 KB Output is correct
6 Correct 5 ms 6800 KB Output is correct
7 Correct 6 ms 6868 KB Output is correct
8 Correct 6 ms 6792 KB Output is correct
9 Correct 6 ms 6996 KB Output is correct
10 Correct 6 ms 6996 KB Output is correct
11 Correct 7 ms 7048 KB Output is correct
12 Correct 6 ms 6996 KB Output is correct
13 Correct 6 ms 6800 KB Output is correct
14 Correct 6 ms 6868 KB Output is correct
15 Correct 12 ms 7368 KB Output is correct
16 Correct 10 ms 7764 KB Output is correct
17 Correct 10 ms 7652 KB Output is correct
18 Correct 10 ms 7888 KB Output is correct
19 Correct 11 ms 7952 KB Output is correct
20 Correct 10 ms 7320 KB Output is correct
21 Correct 12 ms 7636 KB Output is correct
22 Correct 10 ms 7380 KB Output is correct
23 Correct 11 ms 7684 KB Output is correct
24 Correct 11 ms 7492 KB Output is correct
25 Correct 10 ms 7892 KB Output is correct
26 Correct 11 ms 7772 KB Output is correct
27 Correct 9 ms 7384 KB Output is correct
28 Correct 10 ms 7504 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6868 KB Output is correct
2 Correct 6 ms 6996 KB Output is correct
3 Correct 6 ms 6996 KB Output is correct
4 Correct 7 ms 7124 KB Output is correct
5 Correct 6 ms 7124 KB Output is correct
6 Correct 5 ms 6800 KB Output is correct
7 Correct 6 ms 6868 KB Output is correct
8 Correct 6 ms 6792 KB Output is correct
9 Correct 6 ms 6996 KB Output is correct
10 Correct 6 ms 6996 KB Output is correct
11 Correct 7 ms 7048 KB Output is correct
12 Correct 6 ms 6996 KB Output is correct
13 Correct 6 ms 6800 KB Output is correct
14 Correct 6 ms 6868 KB Output is correct
15 Correct 12 ms 7368 KB Output is correct
16 Correct 10 ms 7764 KB Output is correct
17 Correct 10 ms 7652 KB Output is correct
18 Correct 10 ms 7888 KB Output is correct
19 Correct 11 ms 7952 KB Output is correct
20 Correct 10 ms 7320 KB Output is correct
21 Correct 12 ms 7636 KB Output is correct
22 Correct 10 ms 7380 KB Output is correct
23 Correct 11 ms 7684 KB Output is correct
24 Correct 11 ms 7492 KB Output is correct
25 Correct 10 ms 7892 KB Output is correct
26 Correct 11 ms 7772 KB Output is correct
27 Correct 9 ms 7384 KB Output is correct
28 Correct 10 ms 7504 KB Output is correct
29 Correct 66 ms 12776 KB Output is correct
30 Correct 74 ms 15316 KB Output is correct
31 Correct 80 ms 17384 KB Output is correct
32 Correct 71 ms 19816 KB Output is correct
33 Correct 79 ms 19288 KB Output is correct
34 Correct 64 ms 15168 KB Output is correct
35 Correct 80 ms 15848 KB Output is correct
36 Correct 59 ms 13892 KB Output is correct
37 Correct 72 ms 17228 KB Output is correct
38 Correct 67 ms 16708 KB Output is correct
39 Correct 79 ms 20076 KB Output is correct
40 Correct 92 ms 18252 KB Output is correct
41 Correct 55 ms 13968 KB Output is correct
42 Correct 69 ms 15924 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 15400 KB Output is correct
2 Correct 110 ms 18244 KB Output is correct
3 Correct 105 ms 21436 KB Output is correct
4 Correct 135 ms 27808 KB Output is correct
5 Correct 103 ms 23500 KB Output is correct
6 Correct 126 ms 18820 KB Output is correct
7 Correct 120 ms 19888 KB Output is correct
8 Correct 6 ms 6868 KB Output is correct
9 Correct 6 ms 6996 KB Output is correct
10 Correct 6 ms 6996 KB Output is correct
11 Correct 7 ms 7124 KB Output is correct
12 Correct 6 ms 7124 KB Output is correct
13 Correct 5 ms 6800 KB Output is correct
14 Correct 6 ms 6868 KB Output is correct
15 Correct 6 ms 6792 KB Output is correct
16 Correct 6 ms 6996 KB Output is correct
17 Correct 6 ms 6996 KB Output is correct
18 Correct 7 ms 7048 KB Output is correct
19 Correct 6 ms 6996 KB Output is correct
20 Correct 6 ms 6800 KB Output is correct
21 Correct 6 ms 6868 KB Output is correct
22 Correct 12 ms 7368 KB Output is correct
23 Correct 10 ms 7764 KB Output is correct
24 Correct 10 ms 7652 KB Output is correct
25 Correct 10 ms 7888 KB Output is correct
26 Correct 11 ms 7952 KB Output is correct
27 Correct 10 ms 7320 KB Output is correct
28 Correct 12 ms 7636 KB Output is correct
29 Correct 10 ms 7380 KB Output is correct
30 Correct 11 ms 7684 KB Output is correct
31 Correct 11 ms 7492 KB Output is correct
32 Correct 10 ms 7892 KB Output is correct
33 Correct 11 ms 7772 KB Output is correct
34 Correct 9 ms 7384 KB Output is correct
35 Correct 10 ms 7504 KB Output is correct
36 Correct 66 ms 12776 KB Output is correct
37 Correct 74 ms 15316 KB Output is correct
38 Correct 80 ms 17384 KB Output is correct
39 Correct 71 ms 19816 KB Output is correct
40 Correct 79 ms 19288 KB Output is correct
41 Correct 64 ms 15168 KB Output is correct
42 Correct 80 ms 15848 KB Output is correct
43 Correct 59 ms 13892 KB Output is correct
44 Correct 72 ms 17228 KB Output is correct
45 Correct 67 ms 16708 KB Output is correct
46 Correct 79 ms 20076 KB Output is correct
47 Correct 92 ms 18252 KB Output is correct
48 Correct 55 ms 13968 KB Output is correct
49 Correct 69 ms 15924 KB Output is correct
50 Correct 117 ms 20080 KB Output is correct
51 Correct 237 ms 33952 KB Output is correct
52 Correct 203 ms 31400 KB Output is correct
53 Correct 246 ms 40184 KB Output is correct
54 Correct 250 ms 40460 KB Output is correct
55 Correct 207 ms 28364 KB Output is correct
56 Correct 247 ms 30316 KB Output is correct
57 Correct 35 ms 11136 KB Output is correct
58 Correct 215 ms 34872 KB Output is correct
59 Correct 210 ms 32668 KB Output is correct
60 Correct 259 ms 40856 KB Output is correct
61 Correct 244 ms 36720 KB Output is correct
62 Correct 35 ms 11068 KB Output is correct
63 Correct 239 ms 29724 KB Output is correct