제출 #1004589

#제출 시각아이디문제언어결과실행 시간메모리
1004589amirhoseinfar1385Nestabilnost (COI23_nestabilnost)C++17
0 / 100
1547 ms166992 KiB
#include<bits/stdc++.h> using namespace std; const long long maxn=300000+10,lg=19,kaf=(1<<lg); vector<long long>adj[maxn]; long long sz[maxn],all[maxn],wa[maxn],n,inf=1e16,inf2=1e13; struct segment{ struct node{ long long mina,lazy,vis,aval; node(){ mina=0; lazy=0; vis=0; aval=0; } }; long long fen[maxn]; node seg[(1<<(lg+1))]; void ins(long long i,long long w){ seg[kaf+i].mina=w; seg[kaf+i].aval=w; fen[i]=w; } void build(){ for(long long i=kaf-1;i>=1;i--){ seg[i].mina=min(seg[(i<<1)].mina,seg[(i<<1)^1].mina); seg[i].aval=seg[i].mina; } } void calc(long long i){ seg[i].vis=1; if(i>=kaf){ seg[i].mina+=seg[i].lazy; seg[i].lazy=0; return ; } seg[i].mina=min(seg[(i<<1)].mina+seg[(i<<1)].lazy,seg[(i<<1)^1].lazy+seg[(i<<1)^1].mina); } void shift(long long i){ seg[i].vis=1; if(i>=kaf){ return ; } seg[(i<<1)].vis=seg[(i<<1)^1].vis=1; seg[(i<<1)].lazy+=seg[i].lazy; seg[(i<<1)^1].lazy+=seg[i].lazy; seg[i].lazy=0; } void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){ for(int i=l;i<=r;i++){ fen[i]+=w; } return ; if(l>r||l>tr||r<tl||tl>tr){ return ; } if(l>=tl&&r<=tr){ seg[i].lazy+=w; shift(i); calc(i); return ; } shift(i); long long m=(l+r)>>1; upd((i<<1),l,m,tl,tr,w); upd((i<<1)^1,m+1,r,tl,tr,w); calc(i); } long long getmin(long long i,long long l,long long r,long long tl,long long tr){ if(l>r){ return inf; } long long mn=fen[l]; for(int i=l+1;i<=r;i++){ mn=min(mn,fen[i]); } return mn; if(l>r||l>tr||r<tl||tl>tr){ return inf; } shift(i); calc(i); if(l>=tl&&r<=tr){ return seg[i].mina+seg[i].lazy; } long long m=(l+r)>>1; return min(getmin((i<<1),l,m,tl,tr),getmin((i<<1)^1,m+1,r,tl,tr)); } void clear(long long i=1,int l=0,int r=kaf-1,int tl=1,int tr=n+10){ for(int i=l;i<=r;i++){ fen[i]=wa[i]; } return ; if(l>r||l>tr||r<tl||tl>tr||seg[i].vis==0){ return ; } if(l>=tl&&r<=tr){ seg[i].vis=0; seg[i].mina=seg[i].aval; seg[i].lazy=0; } if(l==r){ return ; } int m=(l+r)>>1; clear((i<<1),l,m,tl,tr); clear((i<<1)^1,m+1,r,tl,tr); } }seg; bool cmp(long long a,long long b){ return sz[a]>sz[b]; } void predfs(long long u,long long par=-1){ if(par!=-1){ // adj[u].erase(find(adj[u].begin(),adj[u].end(),par)); sort(adj[u].begin(),adj[u].end()); adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par)); } sz[u]=1; for(auto x:adj[u]){ predfs(x,u); sz[u]+=sz[x]; } sort(adj[u].begin(),adj[u].end(),cmp); } void vorod(){ cin>>n; for(long long i=1;i<=n;i++){ cin>>all[i]; } for(long long i=1;i<=n;i++){ cin>>wa[i]; } for(long long i=0;i<n-1;i++){ long long u,v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } } void pre(){ predfs(1); for(long long i=1;i<=n;i++){ seg.ins(i,wa[i]); } seg.build(); } set<long long>allind[maxn]; long long mainres=0; long long dfs(long long u){ //cout<<u<<endl; long long ret=0; vector<pair<pair<long long,long long>,long long>>alle; for(long long i=1;i<(long long)adj[u].size();i++){ long long v=adj[u][i]; long long re=dfs(v); if(all[v]!=0&&all[v]-1!=all[u]){ mainres+=re; continue; } ret+=re; if(all[v]==all[u]+1){ allind[v].insert(all[v]+1); } deque<long long>tof; for(auto x:allind[v]){ tof.push_back(x); } tof.push_back(n+1); if(all[v]==all[u]+1){ while(tof.front()<=all[v]){ tof.pop_front(); } seg.upd(1,0,kaf-1,1,all[v],inf2); }else{ seg.upd(1,0,kaf-1,1,all[u],inf2); seg.upd(1,0,kaf-1,all[u]+2,n,inf2); tof.clear(); tof.push_back(all[u]+1); tof.push_back(all[u]+2); } for(long long i=0;i<(long long)tof.size()-1;i++){ if(tof[i+1]==tof[i]){ continue; } long long w=seg.getmin(1,0,kaf-1,tof[i],tof[i])-wa[tof[i]]; w-=re; if(w>=0){ continue; } alle.push_back(make_pair(make_pair(tof[i],tof[i+1]-1),w)); } seg.clear(); } //cout<<"ha: "<<u<<endl; if((int)adj[u].size()==0){ return seg.getmin(1,0,kaf-1,all[u]+1,n); } long long v=adj[u][0]; long long re=dfs(v); //cout<<"bar: "<<u<<endl; if(all[v]!=0&&all[v]-1!=all[u]){ mainres+=re; seg.clear(); }else{ swap(allind[u],allind[v]); // ret+=re; // if(u==5){ // //cout<<"tagh: "<<u<<" "<<re<<" "<<seg.getmin(1,0,kaf-1,3,3)<<endl; // } // seg.upd(1,0,kaf-1,1,n,-re); // if(u==5){ // //cout<<"tagh: "<<u<<" "<<re<<" "<<seg.getmin(1,0,kaf-1,3,3)<<endl; // } if(all[v]==all[u]+1){ seg.clear(1,0,kaf-1,1,all[v]); seg.upd(1,0,kaf-1,1,all[v],re); allind[u].insert(all[v]+1); while((*allind[u].begin())<=all[v]){ allind[u].erase((*allind[u].begin())); } }else{ seg.clear(1,0,kaf-1,1,all[u]); seg.clear(1,0,kaf-1,all[u]+2,n); seg.upd(1,0,kaf-1,1,all[u],re); seg.upd(1,0,kaf-1,all[u]+2,n,re); allind[u].clear(); allind[u].insert(all[u]+1); allind[u].insert(all[u]+2); } } //cout<<"hey1: "<<seg.getmin(1,0,kaf-1,1,3)<<endl; for(auto x:alle){ allind[u].insert(x.first.first); seg.upd(1,0,kaf-1,x.first.first,x.first.second,x.second); // if(u==1){ //cout<<"chy: "<<x.first.first<<" "<<x.first.second<<" "<<x.second<<endl; // } } //cout<<"hey2: "<<seg.getmin(1,0,kaf-1,1,3)<<endl; //cout<<"ghablret: "<<ret<<endl; ret+=seg.getmin(1,0,kaf-1,all[u]+1,n); //cout<<"ret: "<<u<<" "<<ret<<endl; return ret; } void solve(){ mainres+=dfs(1); cout<<mainres<<"\n"; } int main(){ ios::sync_with_stdio(0); cin.tie(0); //cout.tie(0); vorod(); pre(); solve(); }

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

code1.cpp: In function 'long long int dfs(long long int)':
code1.cpp:91:15: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   91 |    fen[i]=wa[i];
      |           ~~~~^
code1.cpp:90:16: note: within this loop
   90 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:91:15: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   91 |    fen[i]=wa[i];
      |           ~~~~^
code1.cpp:90:16: note: within this loop
   90 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:91:15: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   91 |    fen[i]=wa[i];
      |           ~~~~^
code1.cpp:90:16: note: within this loop
   90 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:51:10: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   51 |    fen[i]+=w;
      |    ~~~~~~^~~
code1.cpp:50:16: note: within this loop
   50 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:51:10: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   51 |    fen[i]+=w;
      |    ~~~~~~^~~
code1.cpp:50:16: note: within this loop
   50 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:91:15: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   91 |    fen[i]=wa[i];
      |           ~~~~^
code1.cpp:90:16: note: within this loop
   90 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:51:10: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   51 |    fen[i]+=w;
      |    ~~~~~~^~~
code1.cpp:50:16: note: within this loop
   50 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:51:10: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   51 |    fen[i]+=w;
      |    ~~~~~~^~~
code1.cpp:50:16: note: within this loop
   50 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:51:10: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   51 |    fen[i]+=w;
      |    ~~~~~~^~~
code1.cpp:50:16: note: within this loop
   50 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:51:10: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   51 |    fen[i]+=w;
      |    ~~~~~~^~~
code1.cpp:50:16: note: within this loop
   50 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:51:10: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   51 |    fen[i]+=w;
      |    ~~~~~~^~~
code1.cpp:50:16: note: within this loop
   50 |   for(int i=l;i<=r;i++){
      |               ~^~~
code1.cpp:91:15: warning: iteration 300010 invokes undefined behavior [-Waggressive-loop-optimizations]
   91 |    fen[i]=wa[i];
      |           ~~~~^
code1.cpp:90:16: note: within this loop
   90 |   for(int i=l;i<=r;i++){
      |               ~^~~
In member function 'void segment::clear(long long int, int, int, int, int)',
    inlined from 'long long int dfs(long long int)' at code1.cpp:198:12:
code1.cpp:91:10: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' forming offset [2400080, 4194303] is out of the bounds [0, 2400080] of object 'wa' with type 'long long int [300010]' [-Warray-bounds]
   91 |    fen[i]=wa[i];
      |    ~~~~~~^~~~~~
code1.cpp: In function 'long long int dfs(long long int)':
code1.cpp:5:30: note: 'wa' declared here
    5 | long long sz[maxn],all[maxn],wa[maxn],n,inf=1e16,inf2=1e13;
      |                              ^~
In member function 'void segment::clear(long long int, int, int, int, int)',
    inlined from 'long long int dfs(long long int)' at code1.cpp:209:12:
code1.cpp:91:10: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' forming offset [2400080, 4194303] is out of the bounds [0, 2400080] of object 'wa' with type 'long long int [300010]' [-Warray-bounds]
   91 |    fen[i]=wa[i];
      |    ~~~~~~^~~~~~
code1.cpp: In function 'long long int dfs(long long int)':
code1.cpp:5:30: note: 'wa' declared here
    5 | long long sz[maxn],all[maxn],wa[maxn],n,inf=1e16,inf2=1e13;
      |                              ^~
In member function 'void segment::clear(long long int, int, int, int, int)',
    inlined from 'long long int dfs(long long int)' at code1.cpp:228:13:
code1.cpp:91:10: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' forming offset [2400080, 4194303] is out of the bounds [0, 2400080] of object 'wa' with type 'long long int [300010]' [-Warray-bounds]
   91 |    fen[i]=wa[i];
      |    ~~~~~~^~~~~~
code1.cpp: In function 'long long int dfs(long long int)':
code1.cpp:5:30: note: 'wa' declared here
    5 | long long sz[maxn],all[maxn],wa[maxn],n,inf=1e16,inf2=1e13;
      |                              ^~
In member function 'void segment::clear(long long int, int, int, int, int)',
    inlined from 'long long int dfs(long long int)' at code1.cpp:229:13:
code1.cpp:91:10: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' forming offset [2400080, 4194303] is out of the bounds [0, 2400080] of object 'wa' with type 'long long int [300010]' [-Warray-bounds]
   91 |    fen[i]=wa[i];
      |    ~~~~~~^~~~~~
code1.cpp: In function 'long long int dfs(long long int)':
code1.cpp:5:30: note: 'wa' declared here
    5 | long long sz[maxn],all[maxn],wa[maxn],n,inf=1e16,inf2=1e13;
      |                              ^~
In member function 'void segment::clear(long long int, int, int, int, int)',
    inlined from 'long long int dfs(long long int)' at code1.cpp:221:13:
code1.cpp:91:10: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' forming offset [2400080, 4194303] is out of the bounds [0, 2400080] of object 'wa' with type 'long long int [300010]' [-Warray-bounds]
   91 |    fen[i]=wa[i];
      |    ~~~~~~^~~~~~
code1.cpp: In function 'long long int dfs(long long int)':
code1.cpp:5:30: note: 'wa' declared here
    5 | long long sz[maxn],all[maxn],wa[maxn],n,inf=1e16,inf2=1e13;
      |                              ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...