제출 #1230210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230210		Tenis0206	Drawing (CEOI22_drawing)	C++20	15 / 100	1081 ms	589824 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];

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, vector<point> l)
{
    rez[r.poz] = nod;
    if(!st[nod])
    {
        return;
    }
    sort(l.begin(), l.end(), [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 = l.front();
        vector<point> l_st;
        for(int i=1;i<l.size();i++)
        {
            l_st.push_back(l[i]);
        }
        dfs(st[nod], r_st, l_st);
    }
    else
    {
        point r_st = l[w[st[nod]] - 1];
        point r_dr = l[w[st[nod]]];
        vector<point> l_st, l_dr;
        for(int i=0;i<w[st[nod]]-1;i++)
        {
            l_st.push_back(l[i]);
        }
        for(int i=w[st[nod]]+1;i<l.size();i++)
        {
            l_dr.push_back(l[i]);
        }
        dfs(st[nod], r_st, l_st);
        dfs(dr[nod], r_dr, l_dr);
    }
}

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);
    }
    vector<point> v;
    point r = point{0, -1, 0};
    for(int i=1; i<=n; i++)
    {
        point p;
        cin>>p.x>>p.y;
        p.poz = i;
        v.push_back(p);
        if(p.y > r.y)
        {
            r = p;
        }
    }
    vector<point> aux;
    for(auto it : v)
    {
        if(it.poz == r.poz)
        {
            continue;
        }
        aux.push_back(it);
    }
    v = aux;
    int root = 0;
    for(int i=1;i<=n;i++)
    {
        if(G[i].size() != 3)
        {
            root = i;
            break;
        }
    }
    get_sons(root);
    dfs(root, r, v);
    for(int i=1;i<=n;i++)
    {
        cout<<rez[i]<<' ';
    }
    return 0;
}

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