Submission #1227524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227524		spetr	Drawing (CEOI22_drawing)	C++20	100 / 100	219 ms	36084 KiB

Main

#include <bits/stdc++.h>
#include <cmath>
using namespace std;

#define ll long long
const ll mmod = 998244353;  
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

vl ans;
ll pocet = 0; ll root;
vector<pair<double, ll>> uhly;
vll graf;
void dfs(ll v, ll p){
    ll c = 0;
    bool used = false;
    for (ll i = 0; i < graf[v].size(); i++){
        if (graf[v][i] != p){
            dfs(graf[v][i], v);
            c++;
        }
        if (c == 1 && !used && v != root){
            ans[v] = uhly[pocet].second;
            pocet++;
            used = true;
        }
    }
    if (c == 0){
        ans[v] = uhly[pocet].second;
        pocet++;
    }

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;

    graf.resize(n);
    for (ll i = 0; i < n-1; i++){
        ll a,b;
        cin >> a >> b;
        a--; b--;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    vector<pl> body;
    for (ll i = 0; i < n; i++){
        ll a,b;
        cin >> a >> b;
        body.push_back({a,b});
    }
    //Kořen
    root = 0;
    while (graf[root].size() != 1){
        root++;
    }
    ll c_x = body[root].first;
    ll c_y = body[root].second;
    for (ll i = 1; i < n; i++){
        ll x = body[i].first;
        ll y = body[i].second;
        ll dy = c_x-x;
        ll dx = c_y-y;
        double uhel = atan2(dy,dx);
        uhly.push_back({uhel, i});
    
    }
    ans.resize(n, -1);
    sort(uhly.begin(), uhly.end());
    dfs(root, -1);
    ans[root] = 0;

    for (ll i = 0; i < n; i++){
        cout << ans[i] + 1 << " ";
    }

    return 0;
}

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