제출 #763858

#제출 시각아이디문제언어결과실행 시간메모리
763858jamezzzTorrent (COI16_torrent)C++17
0 / 100
115 ms22584 KiB
#include <bits/stdc++.h> using namespace std; #define sf scanf #define pf printf #define pb push_back #define INF 1023456789 #define sz(x) ((int)x.size()) #define all(x) x.begin(),x.end() #define maxn 300005 int n,a,b,dp[maxn],mark[maxn],inc[maxn],far[maxn]; vector<int> AL[maxn]; void dfs1(int u,int p){ if(u==b){ mark[u]=1; return; } for(int v:AL[u]){ if(v==p)continue; dfs1(v,u); if(mark[v]){ mark[u]=1; return; } } } void dfs2(int u,int p){ for(int v:AL[u]){ if(v!=p&&!mark[v])dfs2(v,u); } sort(all(AL[u]),[&](int a,int b){return dp[a]>dp[b];}); int cnt=0; for(int i=0;i<sz(AL[u]);++i){ int v=AL[u][i]; if(v==p||mark[v])continue; inc[v]=++cnt; far[u]=max(far[u],inc[v]+1); dp[u]=max(dp[u],dp[v]+inc[v]); //if(dp[u]==dp[v]+i)far[u]=i+1;//minimum time i can pass down } } int dp2[maxn]; void relax(int u,int p,int t,int mx){//i have a t offset dp2[u]=min(dp2[u],dp[u]+t); int v=-1,add=1; for(int i=0;i<sz(AL[u]);++i){ int o=AL[u][i]; if(o!=p&&mark[o])v=o; else if(o!=p&&!mark[o]){ if(dp[o]+t+inc[o]<=mx)add=min(add,inc[o]+1); else add=far[u]; } } //pf("relax %d %d %d %d: %d %d\n",u,p,t,mx,v,add); if(v!=-1)relax(v,u,t+add+1,mx); } bool can(int x){ //pf("can: %d\n",x); for(int i=1;i<=n;++i){ if(!mark[i]||i==a||i==b)dp2[i]=dp[i]; else dp2[i]=INF; } relax(a,-1,0,x); relax(b,-1,0,x); bool pos=true; for(int i=1;i<=n;++i){ if(dp2[i]>x)pos=false; //if(mark[i])pf("%d: %d\n",i,dp2[i]); } return pos; } int main(){ sf("%d%d%d",&n,&a,&b); for(int i=0;i<n-1;++i){ int x,y;sf("%d%d",&x,&y); AL[x].pb(y); AL[y].pb(x); } dfs1(a,-1); for(int i=1;i<=n;++i){ if(mark[i])dfs2(i,-1); } //for(int i=1;i<=n;++i){ //if(mark[i])pf("%d: %d\n",i,dp[i]); //} //for(int i=1;i<=n;++i)pf("%d ",dp[i]); //pf("\n"); int lo=0,hi=n,mid,res; while(lo<=hi){ mid=(lo+hi)>>1; if(can(mid))hi=mid-1,res=mid; else lo=mid+1; } pf("%d\n",res); }

컴파일 시 표준 에러 (stderr) 메시지

torrent.cpp: In function 'int main()':
torrent.cpp:81:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  sf("%d%d%d",&n,&a,&b);
      |    ^
torrent.cpp:83:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   int x,y;sf("%d%d",&x,&y);
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...