Submission #787583

#	Time	Username	Problem	Language	Result	Execution time	Memory
787583		Valters07	Drawing (CEOI22_drawing)	C++14	0 / 100	129 ms	18412 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5+5;
struct node
{
    int mx, sum, ind;
};
node segt[4*N];
int sub[N], ans[N], ans2[N], n;
vector<int> g[N];
void upd(int p, int val, int sm, int l = 0, int r = n-1, int pos = 1)
{
    if(l==r)
        segt[pos]={val,sm,p};
    else
    {
        int mid = (l+r)/2;
        if(p<=mid)
            upd(p,val,sm,l,mid,pos*2);
        else
            upd(p,val,sm,mid+1,r,pos*2+1);
        if(segt[pos*2].mx>segt[pos*2+1].mx)
            segt[pos]=segt[pos*2];
        else
            segt[pos]=segt[pos*2+1];
        segt[pos].sum=segt[pos*2].sum+segt[pos*2+1].sum;
    }
}
node getmax(int lb, int rb, int l = 0, int r = n-1, int pos = 1)
{
    if(rb<l||r<lb)
        return {-1,0,-1};
    if(lb<=l&&r<=rb)
        return segt[pos];
    int mid = (l+r)/2;
    auto t = getmax(lb,rb,l,mid,pos*2);
    auto t2 =getmax(lb,rb,mid+1,r,pos*2+1);
    if(t.mx>t2.mx)
        return t;
    return t2;
}
node getkth(int k, int l = 0, int r = n-1, int pos = 1)
{
    if(l==r)
        return segt[pos];
    int mid = (l+r)/2, sz = segt[pos*2].sum;
    if(sz>=k)
        return getkth(k,l,mid,pos*2);
    return getkth(k-sz,mid+1,r,pos*2+1);
}
void dfs(int u, int p)
{
    sub[u]=1;
    for(auto v:g[u])
        if(v!=p)
            dfs(v,u),
            sub[u]+=sub[v];
}
void go(int l, int r, int pos, int u, int p)
{
    ans[pos]=u;
    vector<int> ch;
    for(auto v:g[u])
        if(v!=p)
            ch.pb(v);
    upd(pos,-1,0);
    if(ch.empty())
        return;
    if(ch.size()==1)
        go(l,r,getmax(l,r).ind,ch[0],u);
    else
    {
        int mid = getkth(sub[ch[0]]).ind;
        go(l,mid,getmax(l,mid).ind,ch[0],u);
        go(mid+1,r,getmax(mid+1,r).ind,ch[1],u);
    }
}
int main()
{
    fio
//    ifstream cin("in.in");
    cin >> n;
    for(int i = 1;i<n;i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    pair<pair<int,int>,int> p[n];
    for(int i = 0;i<n;i++)
        cin >> p[i].fi.fi >> p[i].fi.se,
        p[i].se=i;
    sort(p,p+n);
    for(int i = 0;i<n;i++)
        upd(i,p[i].fi.se,1);
    dfs(1,1);
    int st = getmax(0,n-1).ind;
    go(0,n-1,st,1,1);
    for(int i = 0;i<n;i++)
        ans2[p[i].se]=ans[i];
    for(int i = 0;i<n;i++)
        cout << ans2[i] << " ";
    return 0;
}

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