Submission #161608

#TimeUsernameProblemLanguageResultExecution timeMemory
161608shayan_pMousetrap (CEOI17_mousetrap)C++14
100 / 100
1123 ms198952 KiB
// Remember... #include<bits/stdc++.h> #define F first #define S second #define PB push_back #define sz(s) int((s).size()) #define bit(n,k) (((n)>>(k))&1) using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int maxn=1e6+10,mod=1e9+7; const ll inf=1e18; vector<int> v[maxn], dps[maxn], path; int dp[maxn], pr[maxn]; bool mark[maxn]; void dfs(int u,int par){ pr[u]=par; int id=-1, cnt=0; for(int y:v[u]){ if(y!=par){ cnt++; dfs(y,u); if(id==-1 || dp[id]<dp[y]) id=y; } } for(int y:v[u]){ if(y!=par && y!=id) dp[u]=max(dp[u], dp[y]); } dp[u]+=cnt; } bool ok(int lm){ int tot=0, usd=0; for(int i=0;i<sz(path);i++){ tot+=sz(dps[i]); } for(int i=0;i<sz(path);i++){ usd++; int pt=0, cnt=0; while(pt<sz(dps[i]) && dps[i][pt]+tot>lm) usd--, pt++, cnt++; lm-=cnt; tot-=sz(dps[i]); if(usd<0 || lm<0) return 0; } return 1; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(); int n,t,m; cin>>n>>t>>m; for(int i=0;i<n-1;i++){ int a,b; cin>>a>>b; v[a].PB(b); v[b].PB(a); } dfs(t,-1); int tmp=m; while(tmp!=t){ mark[tmp]=1; path.PB(tmp); tmp=pr[tmp]; } mark[t]=1; for(int i=0;i<sz(path);i++){ for(int u:v[path[i]]){ if(mark[u]==0) dps[i].PB(dp[u]); } sort(dps[i].begin(),dps[i].end(),greater<int>()); } int l=-1,r=n-1; while(r-l>1){ int mid=(l+r)>>1; if(ok(mid)) r=mid; else l=mid; } return cout<<r<<endl,0; } // Deathly mistakes: // * Read the problem carefully. // * Check maxn. // * Overflows. // #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...