제출 #1012688

#제출 시각아이디문제언어결과실행 시간메모리
1012688JakobZorz봉쇄 시간 (IOI23_closing)C++17
100 / 100
467 ms100644 KiB
#include"closing.h" #include<vector> #include<iostream> #include<queue> #include<set> #include<algorithm> #include<map> using namespace std; typedef __int128 ll; int n,x,y; ll k; vector<pair<int,int>>nodes[200000]; ll distx[200000]; ll disty[200000]; void dfs1(int node,int par,ll*dists){ for(auto[ne,w]:nodes[node]){ if(ne==par) continue; dists[ne]=dists[node]+w; dfs1(ne,node,dists); } } int lvl1(){ vector<bool>vis(n); int res=0; ll kr=k; priority_queue<pair<ll,int>>q; q.push({0,x}); q.push({0,y}); vis[x]=true; vis[y]=true; while(q.size()){ int node=q.top().second; ll cost=-q.top().first; q.pop(); if(cost>kr) break; res++; kr-=cost; for(auto[ne,w]:nodes[node]){ if(vis[ne]) continue; vis[ne]=true; q.push({-min(distx[ne],disty[ne]),ne}); } } return res; } struct Tree{ vector<ll>tree; int size; Tree(int n){ size=1; while(size<n) size*=2; tree=vector<ll>(2*size); } Tree()=default; void upd(int i,ll x){ i+=size; tree[i]=x; while(i!=1){ i/=2; tree[i]=tree[2*i]+tree[2*i+1]; } } int bound(int node,int rl,int rr,ll v){ if(rl==rr-1){ if(tree[node]<=v) return rr; return rl; } int mid=(rl+rr)/2; if(tree[2*node]<=v){ return bound(2*node+1,mid,rr,v-tree[2*node]); }else{ return bound(2*node,rl,mid,v); } } ll sum(int node,int rl,int rr,int x){ if(rr<=x) return tree[node]; if(x<=rl) return 0; int mid=(rl+rr)/2; return sum(2*node,rl,mid,x)+sum(2*node+1,mid,rr,x); } int bound(ll v){ return bound(1,0,size,v); } ll sum(int x){ return sum(1,0,size,x); } }; struct Structure{ vector<ll>vec; Tree tree; Tree pres; map<ll,int>mp; void reg(ll a){ vec.push_back(a); } void init(){ sort(vec.begin(),vec.end()); tree=Tree((int)vec.size()); pres=Tree((int)vec.size()); for(int i=(int)vec.size()-1;i>=0;i--) mp[vec[i]]=i; } int get(ll money){ return pres.sum(tree.bound(money)); } void insert(ll a){ tree.upd(mp[a],vec[mp[a]]); pres.upd(mp[a],1); mp[a]++; } void remove(ll a){ mp[a]--; tree.upd(mp[a],0); pres.upd(mp[a],0); } }; int cmp(pair<ll,ll>a,pair<ll,ll>b){ return a.first+a.second<b.first+b.second; } int solve(vector<pair<ll,ll>>opts,ll money){ sort(opts.begin(),opts.end(),cmp); Structure s; for(auto[i,j]:opts){ s.reg(i); s.reg(j); } s.init(); for(auto[i,j]:opts) s.insert(i); int res=s.get(money); int res2=0; for(auto[i,j]:opts){ money-=i; s.remove(i); s.insert(j); res2++; if(money<0) break; res=max(res,res2+s.get(money)); } return res; } int lvl2(){ int cres=0; ll money=k; vector<pair<ll,ll>>opts; for(int i=0;i<n;i++){ if(distx[i]+disty[i]==distx[y]){ // is on the path from x to y cres++; money-=min(distx[i],disty[i]); opts.emplace_back(max(distx[i],disty[i])-min(distx[i],disty[i]),1e18); }else{ opts.emplace_back(min(distx[i],disty[i]),max(distx[i],disty[i])-min(distx[i],disty[i])); } } if(money<0) return 0; return cres+solve(opts,money); } int max_score(int N,int X,int Y,long long K,vector<int>U,vector<int>V,vector<int>W){ n=N; x=X; y=Y; k=K; for(int i=0;i<n;i++){ distx[i]=0; disty[i]=0; nodes[i].clear(); } for(int i=0;i<n-1;i++){ nodes[U[i]].emplace_back(V[i],W[i]); nodes[V[i]].emplace_back(U[i],W[i]); } dfs1(x,x,distx); dfs1(y,y,disty); return max(lvl1(),lvl2()); }
#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...
#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...