Submission #701089

#	Time	Username	Problem	Language	Result	Execution time	Memory
701089		PurpleCrayon	Drawing (CEOI22_drawing)	C++17	100 / 100	259 ms	40856 KiB

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 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 35 / 35
• Subtask 5: 25 / 25