Submission #1187704

#TimeUsernameProblemLanguageResultExecution timeMemory
1187704PieArmyMousetrap (CEOI17_mousetrap)C++20
45 / 100
714 ms111688 KiB
#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second #define endl '\n' using namespace std; int n,t,r,m; int par[1000023],spec[1000023]; int dp[1000023],ek[1000023]; vector<int>komsu[1000023]; vector<int>res[1000023]; vector<int>specs; int locs[1000023]; void dfs1(int pos){ ek[pos]=ek[par[pos]]+max(0,int(komsu[pos].size())-2+(pos==r)); if(pos==t)ek[pos]=0; for(int x:komsu[pos]){ if(x==par[pos])continue; par[x]=pos; dfs1(x); spec[pos]|=spec[x]; } if(spec[pos]){ specs.pb(pos); } } void dfs2(int pos){ for(int x:komsu[pos]){ if(x==par[pos])continue; if(spec[x])continue; dp[pos]++; dfs2(x); res[pos].pb(dp[x]); } sort(res[pos].begin(),res[pos].end(),[&](const int &x,const int &y){return x>y;}); if(dp[pos]<=1){ return; } dp[pos]+=res[pos][1]; } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n>>t>>r; spec[r]=1; for(int i=1;i<n;i++){ int x,y;cin>>x>>y; komsu[x].pb(y); komsu[y].pb(x); } dfs1(t); specs.pop_back(); int m=specs.size(); for(int i:specs){ dfs2(i); } priority_queue<pair<int,int>>pq; for(int i=0;i<m;i++){ locs[i]=0; if(res[specs[i]].size()){ pq.push({res[specs[i]][locs[i]]+ek[specs[i]],i}); } } int ans=0; for(int i=0;i<m;i++){ while(pq.size()&&pq.top().sc<i)pq.pop(); if(pq.size()){ pair<int,int>p=pq.top(); pq.pop(); locs[p.sc]++; if(locs[p.sc]<res[specs[p.sc]].size()){ pq.push({res[specs[p.sc]][locs[p.sc]]+ek[specs[p.sc]],p.sc}); } } int cur=ek[specs[i]]+(locs[i]>=res[specs[i]].size()?0:res[specs[i]][locs[i]]); ans=max(ans,cur); } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...