Submission #1190205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190205		Unforgettablepl	Drawing (CEOI22_drawing)	C++20	100 / 100	188 ms	39144 KiB

Main

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

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<int>> adj(N+1);
    for(int i=1;i<N;i++){
        int u,v;cin>>u>>v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    int root = -1;
    for(int i=1;i<=N;i++)if(adj[i].size()==1)root=i;
    vector<tuple<int,int,int>> points(N);
    {
        int x=0;
        for(auto&[a,b,c]:points){cin>>a>>b;c=++x;}
    }
    auto minima = *min_element(points.begin(),points.end());
    int ycap = get<1>(minima);
    auto maxima = *max_element(points.begin(),points.end());
    int xmaxi = get<0>(maxima);
    {
        vector<tuple<int,int,int>> upper,lower;
        for(auto&[a,b,c]:points)
            if(b>=ycap and a!=xmaxi)
                upper.emplace_back(a,b,c);
            else
                lower.emplace_back(a,b,c);
        sort(upper.begin(),upper.end());
        sort(lower.rbegin(),lower.rend());
        for(auto&i:lower)upper.emplace_back(i);
        swap(upper,points);
    }
    vector<int> subsize(N+1);
    vector<int> ans(N+1);
    {
        function<int(int,int,int)> dfs = [&](int x,int p,int idx){
            ans[get<2>(points[idx])]=x;
            int alotspace = idx+1;
            for(int&i:adj[x])if(i!=p){
                alotspace = dfs(i,x,alotspace);
            }
            return alotspace;
        };
        assert(dfs(root,0,0)==N);
    }
    for(int i=1;i<=N;i++)cout<<ans[i]<<' ';
    cout << '\n';
}

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