Submission #108869

#TimeUsernameProblemLanguageResultExecution timeMemory
108869fjzzq2002Mousetrap (CEOI17_mousetrap)C++14
45 / 100
1413 ms67676 KiB
#include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #include <time.h> #include <stdlib.h> #include <string> #include <bitset> #include <vector> #include <set> #include <map> #include <queue> #include <algorithm> #include <sstream> #include <stack> #include <iomanip> #include <assert.h> using namespace std; #define pb push_back #define mp make_pair typedef pair<int,int> pii; typedef long long ll; typedef double ld; typedef vector<int> vi; #define fi first #define se second #define fe first #define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);} #define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);} #define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);} #define es(x,e) (int e=fst[x];e;e=nxt[e]) #define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e]) #define SZ 2000555 int n,t,m,fa[SZ],f[SZ]; Edg vector<int> so[1000555]; void dfs(int x) { for esb(x,e,b) if(b!=fa[x]) fa[b]=x,so[x].pb(b),dfs(b); } bool sp[SZ]; void dp(int x) { if(x==m) { f[x]=0; return; } for esb(x,e,b) if(b!=fa[x]) dp(b); vector<ll> ss; ll spp=-8e18; for esb(x,e,b) if(b!=fa[x]) { if(!sp[b]) ss.pb(f[b]+1+so[x].size()-2-sp[x]); //??? else ss.pb(f[b]),spp=f[b]; } sort(ss.begin(),ss.end(),greater<ll>()); if(ss.size()==0) f[x]=0; else if(ss.size()==1) f[x]=!sp[x]; else { if(ss[0]==ss[1]||ss[0]!=spp) f[x]=ss[1]+1; else f[x]=spp; } if(sp[x]) f[x]-=(int)so[x].size()-1; // cout<<x<<"w"<<f[x]<<"\n"; } int main() { scanf("%d%d%d",&n,&m,&t); for(int i=1;i<n;++i) { int a,b; scanf("%d%d",&a,&b); adde(a,b); } dfs(t); ll ans=0; if(t==m) { puts("0"); return 0; } for(int j=m;;j=fa[j]) { sp[j]=1; if(j!=m) ans+=(int)so[j].size()-1; if(j==t) break; } // cerr<<"CA:"<<ans<<"\n"; dp(t); ans+=f[t]; printf("%lld\n",ans); }

Compilation message (stderr)

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&t);
  ~~~~~^~~~~~~~~~~~~~~~~~~
mousetrap.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);
   ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...