Submission #1230345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230345		alexander707070	Drawing (CEOI22_drawing)	C++20	0 / 100	1598 ms	107044 KiB

Main

#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;

struct point{
    int x,y,id;

    inline friend bool operator == (point fr,point sc){
        return fr.x==sc.x and fr.y==sc.y;
    }
}p;

int n,root,a,b,sz[MAXN];
vector<int> v[MAXN],tree[MAXN];
int parent[MAXN],sol[MAXN];
vector<point> w;

void dfs(int x,int p){
    sz[x]=1;
    parent[x]=p;

    for(int i:v[x]){
        if(i==p)continue;
        dfs(i,x);

        tree[x].push_back(i);
        sz[x]+=sz[i];
    }
}

point zero;

double angle(int x,int y){
    return atan2(y,x);
}

bool cmp(point fr,point sc){
    return angle(fr.x-zero.x,fr.y-zero.y) < angle(sc.x-zero.x,sc.y-zero.y);
}

void solve(vector<point> w,int curr){

    if(w.size()==1){
        sol[w[0].id]=curr;
        return;
    }

    int mins=0;
    for(int i=0;i<w.size();i++){
        if(w[i].y<w[mins].y)mins=i;
    }

    zero=w[mins];
    sort(w.begin(),w.end(),cmp);

    int ver=zero.id;
    sol[ver]=curr;

    vector<point> l,r;

    for(int i=0;i<w.size();i++){
        if(w[i]==zero)continue;

        if(int(l.size())<sz[tree[curr][0]]){
            l.push_back(w[i]);
        }else{
            r.push_back(w[i]);
        }
    }

    solve(l,tree[curr][0]);
    if(tree[curr].size()==2)solve(r,tree[curr][1]);
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;

    for(int i=1;i<=n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i=1;i<=n;i++){
        if(v[i].size()<=2)root=i;
    }

    dfs(root,0);

    for(int i=1;i<=n;i++){
        cin>>p.x>>p.y;
        p.id=i;
        
        w.push_back(p);
    }

    solve(w,root);

    for(int i=1;i<=n;i++){
        cout<<sol[i]<<" ";
    }
    cout<<"\n";

    return 0;
}

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