제출 #1037163

#제출 시각아이디문제언어결과실행 시간메모리
10371631L1YAConstruction of Highway (JOI18_construction)C++17
0 / 100
4 ms28764 KiB
//1L1YA #include<bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3,unrool-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; #define Pb push_back #define F first #define S second #define endl '\n' #define sep ' ' #define all(x) x.begin(),x.end() #define al(x,n) x+1,x+n+1 #define SZ(x) ((int)x.size()) #define lc (id<<1) #define rc (lc|1) #define mid (l+r>>1) #define dokme(x) cout << x << endl, exit(0) #define sik(x) cout << x << endl;continue; #define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define FileIO freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll oo=1e18; const int mod=1e9+7; const int inf=1e9+111; const int N=2e5+11; const int lg=19; int n,t=1,a[N],h[N],sz[N],st[N],up[N],fen[N],head[N],seg[N<<2],par[lg][N]; vector<int> G[N]; vector<pii> E(N); void shift(int id){ if(!seg[id]) return; seg[lc]=seg[id];seg[rc]=seg[id]; seg[id]=0; } void update(int ql,int qr,int val,int id=1,int l=1,int r=n+1){ if(qr<=l || ql>=r) return; if(ql<=l && r<=qr){ seg[id]=val; return; } shift(id); update(ql,qr,val,lc,l,mid); update(ql,qr,val,rc,mid,r); } int get(int pos,int id=1,int l=1,int r=n+1){ if(r-l==1) return seg[id]; shift(id); if(pos<mid) return get(pos,lc,l,mid); return get(pos,rc,mid,r); } bool cmp(int x,int y){ return sz[x]>sz[y]; } void dfsset(int v){ sz[v]=1; for(int u: G[v]){ h[u]=h[v]+1; dfsset(u); sz[v]+=sz[u]; } sort(all(G[v]),cmp); } void dfs_hld(int v){ st[v]=t++; if(SZ(G[v])) head[G[v][0]]=head[v]; for(int u: G[v]) dfs_hld(u); } void update_path(int v,int x){ while(head[v]!=1){ update(st[head[v]],st[v]+1,x); v=par[0][head[v]]; } update(1,st[v]+1,x); } int jump(int v,int k){ if(k<0) return v; for(int i=0;i<lg;i++) if(k>>i & 1) v=par[i][v]; return v; } void upd(int x,int y){ for(x=n-x;x<=n;x+=x&-x) fen[x]+=y; } int gett(int x){ int ans=0; for(x=n-x;x;x-=x&-x) ans+=fen[x]; return ans; } int main(){ FastIO cin >> n; vector<int> comp; for(int i=1;i<=n;i++) cin >> a[i],comp.Pb(a[i]); sort(all(comp)); comp.resize(unique(all(comp))-comp.begin()); for(int i=1;i<=n;i++) a[i]=lower_bound(all(comp),a[i])-comp.begin(); for(int i=1;i<n;i++){ int u,v; cin >> u >> v; par[0][v]=u; G[u].Pb(v); E[i]={u,v}; } for(int i=1;i<lg;i++) for(int v=1;v<=n;v++) par[i][v]=par[i-1][par[i-1][v]]; dfsset(1); for(int i=1;i<=n;i++) head[i]=i; dfs_hld(1); update_path(1,1); up[1]=1; for(int i=1;i<n;i++){ int u=E[i].F,v=E[i].S; vector<pii> vc; while(u){ int w=get(st[u]); vc.Pb({w,h[u]-h[up[w]]+1}); int p=jump(w,h[w]-h[u]-1); u=par[0][up[w]]; up[w]=p; } reverse(all(vc)); ll ans=0; for(auto [x,y]: vc) ans+=gett(a[x]+1),upd(a[x],y); cout << ans << endl; for(auto [x,y]: vc) upd(a[x],-y); up[v]=1; update_path(v,v); } return 0; }

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

construction.cpp: In function 'void update(int, int, int, int, int, int)':
construction.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
construction.cpp:54:24: note: in expansion of macro 'mid'
   54 |  update(ql,qr,val,lc,l,mid);
      |                        ^~~
construction.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
construction.cpp:55:22: note: in expansion of macro 'mid'
   55 |  update(ql,qr,val,rc,mid,r);
      |                      ^~~
construction.cpp: In function 'int get(int, int, int, int)':
construction.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
construction.cpp:61:9: note: in expansion of macro 'mid'
   61 |  if(pos<mid) return get(pos,lc,l,mid);
      |         ^~~
construction.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
construction.cpp:61:34: note: in expansion of macro 'mid'
   61 |  if(pos<mid) return get(pos,lc,l,mid);
      |                                  ^~~
construction.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 | #define mid             (l+r>>1)
      |                          ~^~
construction.cpp:62:20: note: in expansion of macro 'mid'
   62 |  return get(pos,rc,mid,r);
      |                    ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...