답안 #701089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701089	2023-02-20T04:54:52 Z	PurpleCrayon	Drawing (CEOI22_drawing)	C++17	100 / 100	259 ms	40856 KB

Main

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #701089

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 15.0 / 15.0

Subtask #3 15.0 / 15.0

Subtask #4 35.0 / 35.0

Subtask #5 25.0 / 25.0

Subtask #1
10.0 / 10.0

Subtask #2
15.0 / 15.0

Subtask #3
15.0 / 15.0

Subtask #4
35.0 / 35.0

Subtask #5
25.0 / 25.0