Submission #782288

#	Time	Username	Problem	Language	Result	Execution time	Memory
782288		Ozy	Drawing (CEOI22_drawing)	C++17	100 / 100	195 ms	34616 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 200000
//para las coordenadas
#define x first
#define y second

lli n,a,b,ini,cont;
lli res[MAX+2];
vector<lli> hijos[MAX+2],orden;
pll coord[MAX+2];

void dfs(lli pos,lli padre){

    if (pos != 1) res[ orden[cont++] ] = pos;
    for(auto h : hijos[pos]) {
        if(h == padre) continue;
        dfs(h,pos);
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
    }

    rep(i,1,n) {
        cin >> a >> b;
        coord[i] = {a,b};
        if (coord[ini].x == 0 || coord[ini].x > a) ini = i;
    }

    rep(i,1,n) {
        if (i==ini) continue;
        orden.push_back(i);
    }

    sort(orden.begin(), orden.end(), [] (lli a, lli b) {
        lli a1 = coord[a].x - coord[ini].x;
        lli b1 = coord[a].y - coord[ini].y;

        lli a2 = coord[b].x - coord[ini].x;
        lli b2 = coord[b].y - coord[ini].y;

        if( (a1*b2) > (a2*b1) ) return true;
        else return false;
    });

    res[ini] = 1;
    cont = 0;
    dfs(1,0);

    rep(i,1,n) cout << res[i] << ' ';

    return 0;
}

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