제출 #236403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236403		LittleFlowers__	Construction of Highway (JOI18_construction)	C++17	100 / 100	447 ms	20972 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

const int N=100010,
          INF=1e9;

int n,it;
int uu[N],vv[N];
int a[N],sz[N],d[N],w[N],bit[N],st[N],ed[N],par[N],dep[N],id[N];
vector<int> val;
vector<int> ad[N];

vector<ii> mp[N];

void dfs1(int u){
    sz[u]=1;
    forv(v,ad[u]){
        dep[v]=dep[u]+1;
        par[v]=u;
        dfs1(v);
        sz[u]+=sz[v];
        if(sz[d[u]]<sz[v]) d[u]=v;
    }
}
void dfs2(int u){
    st[u]=++it;
    if(!w[u]) w[u]=u;
    if(d[u])  w[d[u]]=w[u], dfs2(d[u]);
    forv(v,ad[u]) if(v!=d[u]) dfs2(v);
    ed[u]=it;
}

vector<int> rev;

void upd(int i,int x){
    for(;i<=val.size();i+=i&-i){
        bit[i]+=x;
        rev.push_back(i);
    }
}
int que(int i){
    if(i>val.size()) return 0;
    int ret=0;
    for(;i;i-=i&-i) ret+=bit[i];
    return ret;
}

vector<ii> take(int u,int v){ /// take element beginning from v in set_u
    /// mp stores elements from leaf to root
    int sz=dep[v]-dep[w[u]]+1;
    vector<ii> inq;
    vector<ii>&val=mp[u];
    fordec(j,val.size()-1,0){
        if(sz<=val[j].se){
            inq.push_back({val[j].fi,sz});
            break;
        }
        sz-=val[j].se;
        inq.push_back(val[j]);
    }
    reverse(all(inq));
    return inq;
}

int mode;

void modify(int u,int v,int we){
    int sz=dep[v]-dep[w[u]]+1;
    vector<ii>&val=mp[u];
    for(;;){
        if(sz<=val.back().se){
            if(sz<val.back().se){
                val.back()={val.back().fi,val.back().se-sz};
            } else val.pop_back();
            break;
        }
        sz-=val.back().se;
        val.pop_back();
    }
    val.push_back({we,dep[v]-dep[w[u]]+1});

}

main(){
    #define task "vim"
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);

    forinc(i,1,n=in) val.push_back(a[i]=in);

    sort(all(val)), val.erase(unique(all(val)),val.end());
    forinc(i,1,n) a[i]=lower_bound(all(val),a[i])-val.begin()+1;

    forinc(i,2,n){
        uu[i]=in, vv[i]=in;
        ad[uu[i]].push_back(vv[i]);
    }

    dfs1(1);
    dfs2(1);


    //forinc(i,1,n) cout<<i<<" "<<d[i]<<"\n";

    forinc(i,1,n) if(!d[i]){
        mp[i].push_back({INF,dep[i]-dep[w[i]]+1});
        int j=i;
        for(;;){
            id[j]=i;
            if(j==w[i]) break;
            j=par[j];
        }
    }
    forinc(i,2,n){
        int p=uu[i], u=vv[i];

        vector<int> path;
        int j=p;
        int tot=0;
        while(j){
                if(0)
            if(i==5){
                cerr<<id[j]<<" "<<j<<"\n";
                forv(t,take(id[j],j))
                cerr<<t.fi<<" "<<t.se<<"\n";
                gg
            }
            forv(t,take(id[j],j)){
                //if(i==5)
                    //cerr<<id[j]<<" "<<j<<"\n";
                     //cerr<<t.fi<<" "<<t.se<<"\n";
                tot+=que(t.fi-1)*t.se;
                //if(i==5) cerr<<tot<<"\n";
                upd(t.fi,t.se);
            }
            j=par[w[j]];
        }
        //if(i==5) gg

        cout<<tot<<"\n";
        //cerr<<tot<<"\n";
        j=u;
        while(j){
            modify(id[j],j,a[u]);
            j=par[w[j]];
        }
        //if(i==4) gg

        forv(j,rev) bit[j]=0;
        rev.clear();
        if(i==3){
            //forv(j,mp[8]) cerr<<j.fi<<" "<<j.se<<"\n";
            //gg
        }
    }

}

컴파일 시 표준 에러 (stderr) 메시지

construction.cpp: In function 'void upd(int, int)':
construction.cpp:54:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;i<=val.size();i+=i&-i){
          ~^~~~~~~~~~~~
construction.cpp: In function 'int que(int)':
construction.cpp:60:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i>val.size()) return 0;
        ~^~~~~~~~~~~
construction.cpp: At global scope:
construction.cpp:102:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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