Submission #701084

#	Time	Username	Problem	Language	Result	Execution time	Memory
701084		PurpleCrayon	Drawing (CEOI22_drawing)	C++17	30 / 100	1572 ms	17292 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 y < he.y;
    }
};

int n, sub[N], ans[N];
vector<int> adj[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];
}

void dfs(int c, int p, vector<P>& pts, int l, int r) {
    int use = -1;
    for (int i = l; i <= r; i++) if (!pts[i].dead)
        if (use == -1 || pts[i] < pts[use])
            use = i;

    assert(use != -1);

    ans[pts[use].id] = c; pts[use].dead = 1;

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

    if (one == -1) return;
    if (two == -1) {
        dfs(one, c, pts, l, r);
    } else {
        int cnt = 0;
        for (int m = l; m <= r; m++) if (!pts[m].dead) {
            cnt++;
            if (cnt == sub[one])
                dfs(one, c, pts, l, m), dfs(two, c, pts, m + 1, 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;
    }

    dfs(root, -1, pts, 0, n-1);

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