제출 #1094920

#제출 시각아이디문제언어결과실행 시간메모리
1094920HoriaHaivasMousetrap (CEOI17_mousetrap)C++14
25 / 100
571 ms99920 KiB
/* "care a facut teste cu Lattice reduction attack e ciudat" "linistiti va putin" - 2023 - */ #include<bits/stdc++.h> #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " #pragma GCC optimize("Ofast") #define int long long using namespace std; struct Node { int maxval; int maxvalpoz; int minval; int minvalpoz; int lazy; }; int dp[1000005]; /// dp[u] = costul sa il fortam pe soricel sa se intoarca la u vector<int> nodes[1000005]; int depth[1000005]; int p[1000005]; int nxt[1000005]; int variante[1000005]; int lim[1000005]; int leftie[1000005]; int n,t,m,cnt; const int INF=1e9; ///AINT class AINT { private: Node aint[4000005]; public: void prop(int val) { if (aint[val].lazy==0) return; aint[val].maxval+=aint[val].lazy; aint[val].minval+=aint[val].lazy; if (val*2+1<=4*n) { aint[val*2].lazy+=aint[val].lazy; aint[val*2+1].lazy+=aint[val].lazy; } aint[val].lazy=0; } void build(int l, int r, int val, int num) { if (l==r) { if (num==1) { aint[val]= {variante[l],l,variante[l],l,0}; } else { aint[val]= {lim[l],l,lim[l],l,0}; } return; } int mid; mid=(l+r)/2; build(l,mid,val*2,num); build(mid+1,r,val*2+1,num); aint[val]=combine(aint[val*2],aint[val*2+1]); } void lazy_update(int l, int r, int val, int qa, int qb, int x) { prop(val); if (qa<=l && r<=qb) { aint[val].lazy+=x; return; } int mid; mid=(l+r)/2; if (qa<=mid) lazy_update(l,mid,val*2,qa,qb,x); if (qb>mid) lazy_update(mid+1,r,val*2+1,qa,qb,x); prop(val*2); prop(val*2+1); aint[val]=combine(aint[val*2],aint[val*2+1]); } Node query(int l, int r, int val, int qa, int qb) { prop(val); if (qa<=l && r<=qb) { return aint[val]; } Node ans; int mid; ans= {-INF,0,INF,0,0}; mid=(l+r)/2; if (qa<=mid) ans=combine(ans,query(l,mid,val*2,qa,qb)); if (qb>mid) ans=combine(ans,query(mid+1,r,val*2+1,qa,qb)); return ans; } void disable(int l, int r, int val, int poz) { prop(val); if (l==r) { aint[val]= {-INF,0,INF,0,0}; return; } int mid; mid=(l+r)/2; if (poz<=mid) disable(l,mid,val*2,poz); else disable(mid+1,r,val*2+1,poz); prop(val*2); prop(val*2+1); aint[val]=combine(aint[val*2],aint[val*2+1]); } Node combine(Node a, Node b) { Node c; if (a.minval!=b.minval) { if (a.minval<b.minval) { c.minval=a.minval; c.minvalpoz=a.minvalpoz; } else { c.minval=b.minval; c.minvalpoz=b.minvalpoz; } } else { if (a.minvalpoz<b.minvalpoz) { c.minval=a.minval; c.minvalpoz=a.minvalpoz; } else { c.minval=b.minval; c.minvalpoz=b.minvalpoz; } } if (a.maxval!=b.maxval) { if (a.maxval>b.maxval) { c.maxval=a.maxval; c.maxvalpoz=a.maxvalpoz; } else { c.maxval=b.maxval; c.maxvalpoz=b.maxvalpoz; } } else { if (a.maxvalpoz<b.maxvalpoz) { c.maxval=a.maxval; c.maxvalpoz=a.maxvalpoz; } else { c.maxval=b.maxval; c.maxvalpoz=b.maxvalpoz; } } c.lazy=0; return c; } } aint1, aint2; void calc(int node, int parent) { int mx1,mx2; mx1=0; mx2=0; for (auto x : nodes[node]) { if (x!=parent) calc(x,node); if (dp[x]>mx1) { mx2=mx1; mx1=dp[x]; } else if (dp[x]>mx2) { mx2=dp[x]; } } dp[node]=1+mx2+(nodes[node].size()-1-2)+1; } void dfs(int node, int parent) { for (auto x : nodes[node]) { if (x!=parent) { p[x]=node; depth[x]=depth[node]+1; dfs(x,node); } } } void build_path(int l, int r) { int cr,cl,start,sofar,pending,len,last; cr=r; cl=l; len=0; while (depth[r]>depth[l]) { nxt[p[r]]=r; r=p[r]; len++; } while (depth[l]>depth[r]) { nxt[p[l]]=l; l=p[l]; len++; } while (r!=l) { nxt[r]=p[r]; nxt[p[l]]=l; l=p[l]; r=p[r]; len+=2; } len++; r=cr; l=cl; cnt=0; sofar=0; last=0; while (l!=r) { start=cnt; pending=0; for (auto x : nodes[l]) { if (x!=nxt[l] && x!=last) { pending++; } } sofar+=pending; for (auto x : nodes[l]) { if (x!=nxt[l] && x!=last) { calc(x,l); variante[++cnt]=dp[x]+sofar; lim[cnt]=len; leftie[cnt]=start; } } last=l; l=nxt[l]; len--; } start=cnt; pending=0; for (auto x : nodes[l]) { if (x!=nxt[l] && x!=last) { pending++; } } sofar+=pending; for (auto x : nodes[l]) { if (x!=nxt[l] && x!=last) { calc(x,l); variante[++cnt]=dp[x]+sofar; lim[cnt]=len; leftie[cnt]=start; } } } signed main() { //ifstream fin("secvp.in"); //ofstream fout("secvp.out"); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int u,v,i,lbound; Node ans,ans2; bool ok; cin >> n >> t >> m; for (i=1; i<=n-1; i++) { cin >> u >> v; nodes[u].push_back(v); nodes[v].push_back(u); } depth[1]=1; dfs(1,-1); build_path(t,m); aint1.build(0,cnt,1,1); aint2.build(0,cnt,1,2); ok=true; while (ok) { ans=aint1.query(0,cnt,1,0,cnt); lbound=leftie[ans.maxvalpoz]; ans2=aint2.query(0,cnt,1,1,max(1LL,lbound)); if (ans2.minval==0) { cout << ans.maxval; return 0; } else { aint1.disable(0,cnt,1,ans.maxvalpoz); aint1.lazy_update(0,cnt,1,0,lbound,1); aint2.lazy_update(0,cnt,1,1,max(1LL,lbound),-1); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...