Submission #973000

#	Time	Username	Problem	Language	Result	Execution time	Memory
973000		berr	Drawing (CEOI22_drawing)	C++17	100 / 100	174 ms	31544 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;

    vector<vector<int>> g(n);

    for(int i=1; i<n; i++){
        int x, y; cin >> x >> y;
        x--; y--;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    int r=0, r2=0;

    vector<array<int, 2>> e(n);

    for(auto &[i, l]: e){
        cin >> i >> l;
    }        

    for(int i=0; i<n; i++){
        if(g[i].size()==3) r2 = i;
        if(e[i][1] < e[r][1]) r=i;
        else if(e[i][1]==e[r][1] && e[i][0] > e[r][0]) r=i;
    }


    vector<int> id(n-1);

    int pos=0;

    for(int i=0; i<n-1; i++){
        if(r==pos) pos++;
        id[i]=pos; pos++;
    }

    auto x=[&](int a, int b){
        return e[a][0]-e[b][0];
    };
    auto y=[&](int a, int b){
        return e[a][1]-e[b][1];
    };

    auto check=[&](int r, int a, int b){
        return y(b, r)*x(a, r) < y(a, r)*x(b, r);
    };
    sort(id.begin(), id.end(), [&](int x, int y){
        return check(r, x, y);
    });
    vector<int> vis(n, -1);

    id.push_back(r);

    auto dfs=[&](int v, int p, auto&&dfs)->void{
        
        vis[id.back()] = v; id.pop_back();
         for(auto i: g[v]){
            if(i==p) continue;
            dfs(i, v, dfs);
        }
    };
    dfs(r2, r2, dfs);

    for(int i=0; i<n; i++) cout<<vis[i]+1<<" ";

}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 35 / 35
• Subtask 5: 25 / 25