Submission #373544

#TimeUsernameProblemLanguageResultExecution timeMemory
373544i_am_noobConstruction of Highway (JOI18_construction)C++14
100 / 100
1020 ms41836 KiB
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,avx512f") #include<bits/stdc++.h> //#pragma GCC optimize("Ofast,unroll-loops") using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define rep(a) rep1(i,a) #define rep1(i,a) rep2(i,0,a) #define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++) #define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--) #define all(a) a.begin(),a.end() #define pii pair<int,int> #define pb push_back #define inf 1010000000 //#define inf 4000000000000000000 #define eps 1e-9 #define sz(a) ((int)a.size()) #define pow2(x) (1ll<<(x)) #define ceiling(a,b) (((a)+(b)-1)/(b)) #ifdef i_am_noob #define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__) template<typename T> void _do(T && x) {static int cnt=0;cerr << x << endl;cnt++;if(cnt>1000) exit(0);} template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);} #else #define bug(...) 826 #endif inline char readchar(){ const int maxn=1000000; static char buf[maxn],*p=buf,*q=buf; if(p==q&&(q=(p=buf)+fread(buf,1,maxn,stdin))==buf) return EOF; else return *p++; } inline int readint(){ int c=readchar(),x=0,neg=0; while((c<'0'||c>'9')&&c!='-'&&c!=EOF) c=readchar(); if(c=='-') neg=1,c=readchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=readchar(); return neg?-x:x; } const int Mod=1000000007,Mod2=998244353; const int MOD=Mod; const int maxn=100005; //i_am_noob int n,a[maxn],e[maxn][2],fa[maxn],dep[maxn],siz[maxn],tour[maxn],cur,val[2*maxn][18],id[maxn],to[maxn],head[maxn],bit[maxn],tail[4*maxn],tag[4*maxn]; vector<int> vec,adj[maxn],child[maxn]; vector<pii> opers; void dfs(int u, int par){ fa[u]=par; dep[u]=par==-1?0:dep[par]+1; siz[u]=1; tour[u]=cur; val[cur++][0]=u; for(auto v: adj[u]) if(v!=par){ dfs(v,u); val[cur++][0]=u; siz[u]+=siz[v]; } } void dfs2(int u, int par, int h){ to[u]=-1,head[u]=h,id[u]=cur++; if(par>=0) child[par].pb(u); for(auto v: adj[u]) if(v!=par) if(to[u]==-1||siz[v]>siz[to[u]]) to[u]=v; if(to[u]>=0) dfs2(to[u],u,h); for(auto v: adj[u]) if(v!=par&&v!=to[u]) dfs2(v,u,v); } bool cmp(int i, int j){return dep[i]<dep[j];} int querylca(int u, int v){ int l=tour[u],r=tour[v]; if(l>r) swap(l,r); int x=__lg(r-l+1); return min(val[l][x],val[r-pow2(x)+1][x],cmp); } void modifybit(int p, int x){for(p++; p<maxn; p+=p&-p) bit[p]+=x;} int querybit(int l, int r){ int res=0; for(r++; r; r-=r&-r) res+=bit[r]; for(; l; l-=l&-l) res-=bit[l]; return res; } void push(int k, int l, int r){ if(l!=r){ if(tag[k]!=-1){ tag[k<<1]=tag[k],tag[k<<1|1]=tag[k]; tail[k<<1]=tag[k],tail[k<<1|1]=tag[k]; } } tag[k]=-1; } void build(int k, int l, int r){ if(l==r){ tail[k]=0; return; } int mid=l+r>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r); } void modifyseg(int k, int l, int r, int ql, int qr, int x){ if(l>qr||r<ql) return; if(ql<=l&&qr>=r){ tail[k]=tag[k]=x; return; } int mid=l+r>>1; push(k,l,r); modifyseg(k<<1,l,mid,ql,qr,x),modifyseg(k<<1|1,mid+1,r,ql,qr,x); } int queryseg(int k, int l, int r, int p){ if(l==r) return tail[k]; int mid=l+r>>1; push(k,l,r); if(p<=mid) return queryseg(k<<1,l,mid,p); return queryseg(k<<1|1,mid+1,r,p); } void modify(int u, int x){ int v; while(1){ v=head[u]; modifyseg(1,0,maxn-1,id[v],id[u],x); if(v==0) break; u=fa[v]; } } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0); #ifdef i_am_noob freopen("input1.txt","r",stdin); freopen("output1.txt","w",stdout); freopen("output2.txt","w",stderr); #endif n=readint(); rep(n) a[i]=readint(); rep(n) vec.pb(a[i]); sort(all(vec)); vec.resize(unique(all(vec))-vec.begin()); rep(n) a[i]=lower_bound(all(vec),a[i])-vec.begin(); rep(n-1) e[i][0]=readint(),e[i][1]=readint(); rep(n-1) e[i][0]--,e[i][1]--; rep(n-1) adj[e[i][0]].pb(e[i][1]),adj[e[i][1]].pb(e[i][0]); cur=0; dfs(0,-1); rep2(j,1,18) rep(2*n-pow2(j)) val[i][j]=min(val[i][j-1],val[i+pow2(j-1)][j-1],cmp); cur=0; dfs2(0,-1,0); rep(4*maxn) tag[i]=-1; build(1,0,maxn-1); rep(n-1){ int u=e[i][0],v=e[i][1],x=0,y,z,t,tot=0; ll ans=0; opers.clear(); while(1){ y=queryseg(1,0,maxn-1,id[x]); z=querylca(u,y); ans+=1ll*(tot-querybit(0,a[y]))*(dep[z]-dep[x]+1); if(z==u) break; modifybit(a[y],dep[z]-dep[x]+1); opers.pb({a[y],-dep[z]+dep[x]-1}); tot+=dep[z]-dep[x]+1; x=*--upper_bound(all(child[z]),u,[](int i, int j){return id[i]<id[j];}); } for(auto& [p,q]: opers) modifybit(p,q); modify(v,v); cout << ans << "\n"; } return 0; }

Compilation message (stderr)

construction.cpp: In function 'void build(int, int, int)':
construction.cpp:106:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int mid=l+r>>1;
      |             ~^~
construction.cpp: In function 'void modifyseg(int, int, int, int, int, int)':
construction.cpp:116:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |     int mid=l+r>>1;
      |             ~^~
construction.cpp: In function 'int queryseg(int, int, int, int)':
construction.cpp:123:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |     int mid=l+r>>1;
      |             ~^~
construction.cpp: In function 'int main()':
construction.cpp:176:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  176 |         for(auto& [p,q]: opers) modifybit(p,q);
      |                   ^
construction.cpp:163:41: warning: unused variable 't' [-Wunused-variable]
  163 |         int u=e[i][0],v=e[i][1],x=0,y,z,t,tot=0;
      |                                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...