제출 #1230267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230267		Tenis0206	Drawing (CEOI22_drawing)	C++20	100 / 100	169 ms	40012 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, point r, int cnt)
{
    rez[r.poz] = nod;
    if(!st[nod])
    {
        return;
    }
    sort(v + 1, v + cnt + 1, [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);
    });
    if(!dr[nod])
    {
        point r_st = v[cnt];
        dfs(st[nod], r_st, cnt - 1);
    }
    else
    {
        point r_st = v[w[st[nod]]];
        point r_dr = v[w[st[nod]] + 1];
        dfs(st[nod], r_st, w[st[nod]] - 1);
        int nr = 0;
        for(int i=w[st[nod]]+2; i<=cnt; i++)
        {
            aux[++nr] = v[i];
        }
        aux[++nr] = v[w[st[nod]] + 1];
        aux[++nr] = v[w[st[nod]]];
        for(int i=1; i<w[st[nod]]; i++)
        {
            aux[++nr] = v[i];
        }
        for(int i=1; i<=cnt; i++)
        {
            v[i] = aux[i];
        }
        dfs(dr[nod], r_dr, w[dr[nod]] - 1);
    }
}

void dfs2(int nod)
{
    ++poz;
    rez[v[poz].poz] = nod;
    if(st[nod])
    {
        dfs2(st[nod]);
    }
    if(dr[nod])
    {
        dfs2(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;
        }
    }
    if(false)
    {
        get_sons(root);
        dfs(root, r, n - 1);
    }
    else
    {
        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);
        dfs2(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