Submission #1230462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230462		alexander707070	Drawing (CEOI22_drawing)	C++20	100 / 100	176 ms	45896 KiB

Main

#include<bits/stdc++.h>
#define MAXN 200007
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];
    }

    if(tree[x].size()==2 and sz[tree[x][0]]>sz[tree[x][1]])swap(tree[x][0],tree[x][1]);
}

point zero;

const double inf=1e9;

double angle(double x,double y){
    if(x==0)return 0;

    if(y==0){
        if(x<=0)return -inf;
        else return inf;
    }

    return x/y;
}

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];

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

    if(tree[curr].size()==1){
        for(int i=0;i<w.size();i++){
            if(w[i]==zero){
                swap(w[i],w[w.size()-1]);
                w.pop_back(); break;
            }
        }

        solve(w,tree[curr][0]);
        return;
    }

    if(sz[tree[curr][0]]<=15){
        for(int i=0;i<w.size();i++){
            if(w[i]==zero){
                swap(w[i],w[w.size()-1]);
                w.pop_back(); break;
            }
        }

        vector<point> l;

        for(int t=0;t<sz[tree[curr][0]];t++){
            
            point mins=w[0];

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

            l.push_back(mins);

            for(int i=0;i<w.size();i++){
                if(w[i]==mins){
                    swap(w[i],w[w.size()-1]);
                    w.pop_back(); break;
                }
            }
        }

        solve(l,tree[curr][0]);
        solve(w,tree[curr][1]);
        return;
    }
    
    sort(w.begin(),w.end(),cmp);

    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]);
}

void solve2(int l,int r,int curr){
    if(l==r){
        sol[w[l].id]=curr;
        return;
    }

    sol[w[l].id]=curr;
    solve2(l+1,l+sz[tree[curr][0]],tree[curr][0]);
    if(tree[curr].size()==2){
        solve2(r-sz[tree[curr][1]]+1,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);
    }

    if(n<=10000){
        solve(w,root);

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

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

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

    solve2(0,w.size()-1,root);

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

    return 0;
}

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