Submission #1230290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230290		Tenis0206	Drawing (CEOI22_drawing)	C++20	100 / 100	174 ms	40008 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int nmax = 2e5;

struct point
{
    int x, y, poz;
};

int n;
vector<int> G[nmax + 5];

int w[nmax + 5];
int st[nmax + 5], dr[nmax + 5];

int rez[nmax + 5];

point v[nmax + 5];

point aux[nmax + 5];

int poz = 0;

void get_sons(int nod, int dad = 0)
{
    w[nod] = 1;
    for(auto it : G[nod])
    {
        if(it == dad)
        {
            continue;
        }
        if(!st[nod])
        {
            st[nod] = it;
        }
        else
        {
            dr[nod] = it;
        }
        get_sons(it, nod);
        w[nod] += w[it];
    }
}

void dfs(int nod)
{
    ++poz;
    rez[v[poz].poz] = nod;
    if(st[nod])
    {
        dfs(st[nod]);
    }
    if(dr[nod])
    {
        dfs(dr[nod]);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n;
    for(int i=1; i<n; i++)
    {
        int x, y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    point r = point{0, -1, 0};
    for(int i=1; i<=n; i++)
    {
        point p;
        cin>>p.x>>p.y;
        p.poz = i;
        v[i] = p;
        if(p.y > r.y)
        {
            r = p;
        }
    }
    int nr = 0;
    for(int i=1; i<=n; i++)
    {
        if(v[i].poz == r.poz)
        {
            continue;
        }
        aux[++nr] = v[i];
    }
    for(int i=1; i<n; i++)
    {
        v[i] = aux[i];
    }
    int root = 0;
    for(int i=1; i<=n; i++)
    {
        if(G[i].size() != 3)
        {
            root = i;
            break;
        }
    }
    sort(v + 1, v + n, [r](point a, point b)
    {
        int d = (1LL * a.x * r.y + 1LL * r.x * b.y + 1LL * b.x * a.y) - (1LL * a.y * r.x + 1LL * r.y * b.x + 1LL * b.y * a.x);
        return (d < 0);
    });
    for(int i=n; i>=2; i--)
    {
        v[i] = v[i - 1];
    }
    v[1] = r;
    get_sons(root);
    dfs(root);
    for(int i=1; i<=n; i++)
    {
        cout<<rez[i]<<' ';
    }
    return 0;
}

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