Submission #219602

#	Time	Username	Problem	Language	Result	Execution time	Memory
219602		thebes	Construction of Highway (JOI18_construction)	C++14	100 / 100	634 ms	150700 KiB

construction

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

namespace output{
    void __(short x){cout<<x;}
    void __(unsigned x){cout<<x;}
    void __(int x){cout<<x;}
    void __(long long x){cout<<x;}
    void __(unsigned long long x){cout<<x;}
    void __(double x){cout<<x;}
    void __(long double x){cout<<x;}
    void __(char x){cout<<x;}
    void __(const char*x){cout<<x;}
    void __(const string&x){cout<<x;}
    void __(bool x){cout<<(x?"true":"false");}
    template<class S,class T>
    void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
    template<class T>
    void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class S,class T>
    void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    void pr(){cout<<"\n";}
    template<class S,class... T>
    void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}

using namespace output;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,char> pic;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;

#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)

struct Treap{
    struct nd{
        int p, sz, sm, k; nd *l, *r;
        nd(int key,int size):p(rand()),sz(size),sm(size),k(key),l(0),r(0){}
    }*rt=NULL,*l,*r,*t;
    void clear(){
        rt=l=r=t=NULL;
    }
    inline int sz(nd *n){return n?n->sz:0;}
    inline int sm(nd *n){return n?n->sm:0;}
    inline void upd(nd *&n){
        if(!n) return;
        n->sm=sm(n->l)+sm(n->r)+sz(n);
    }
    void split(nd *n,nd *&l,nd *&r,int k){
        if(!n) l=r=NULL;
        else if(n->k<=k) split(n->r,n->r,r,k),l=n;
        else split(n->l,l,n->l,k),r=n;
        upd(n);
    }
    void mrg(nd *&n,nd *l,nd *r){
        if(!l||!r) n=l?l:r;
        else if(l->p>r->p) mrg(l->r,l->r,r),n=l;
        else mrg(r->l,l,r->l),n=r;
        upd(n);
    }
    ll insert(int key,int size){
        split(rt,l,r,key);
        split(l,l,t,key-1);
        ll ret = 1LL*size*sm(l);
        if(!t) t=new nd(key,size);
        else t->sz+=size,t->sm+=size;
        mrg(l,l,t);
        mrg(rt,l,r);
        return ret;
    }
}treap;

const int MN = 1e5+5;
ll N, c[MN], i, x, y, id[MN], sz[MN], len[MN], par[MN], lnk[MN], nxt, stid, pos[MN];
struct idk{ll st, ed, val;};
stack<idk> hld[MN];
vl adj[MN]; pll ed[MN], big[MN];

void dfs(ll n){
    sz[n] = 1;
    big[n]={-1,-1};
    for(auto v : adj[n]){
        par[v] = n;
        dfs(v);
        sz[n] += sz[v];
        if(sz[v]>big[n].first)
            big[n]={sz[v],v};
    }
    if(big[n].second!=-1) len[n]=1+len[big[n].second];
}

void dfs2(ll n){
    if(!lnk[n]){
        lnk[n]=n; pos[n]=++nxt; nxt+=len[n];
        id[n]=++stid; 
    }
    else{
        pos[n]=pos[par[n]]+1; 
        id[n]=id[par[n]];
    }
    for(auto v : adj[n]){
        if(v==big[n].second) lnk[v] = lnk[n];
        dfs2(v);
    }
}

int main(){
    srand(time(0));
    for(scanf("%lld",&N),i=1;i<=N;i++)
        scanf("%lld",&c[i]);
    for(i=1;i<N;i++){
        scanf("%lld%lld",&x,&y);
        adj[x].pb(y);
        ed[i]={x,y};
    }
    dfs(1); dfs2(1);
    hld[id[1]].push({pos[1],pos[1],c[1]});
    for(i=1;i<N;i++){
        treap.clear();
        ll ans = 0, cur = ed[i].second, rep, st, tmp, col=c[ed[i].second];
        vector<pll> blk;
        while(cur){
            rep = lnk[cur]; blk.clear();
            st = id[rep];
            while(hld[st].size()){
                if(hld[st].top().ed<=pos[cur]){
                    blk.pb({hld[st].top().ed-hld[st].top().st+1,hld[st].top().val});
                    hld[st].pop();
                }
                else{
                    blk.pb({pos[cur]-hld[st].top().st+1,hld[st].top().val});
                    tmp=hld[st].top().ed; hld[st].pop();
                    hld[st].push({pos[cur]+1,tmp,blk.back().second});
                    break;
                }
            }
            hld[st].push({pos[rep],pos[cur],col});
            reverse(blk.begin(),blk.end());
            for(auto v : blk){
                ans += treap.insert(v.second,v.first);
            }
            cur = par[rep];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:122:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%lld",&N),i=1;i<=N;i++)
         ~~~~~~~~~~~~~~~~^~~~
construction.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&c[i]);
         ~~~~~^~~~~~~~~~~~~~
construction.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&x,&y);
         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84