제출 #236403

#제출 시각아이디문제언어결과실행 시간메모리
236403LittleFlowers__Construction of Highway (JOI18_construction)C++17
100 / 100
447 ms20972 KiB
#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(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...