oj.uz

Submission #763860

# Submission time Handle Problem Language Result Execution time Memory
763860 2023-06-23T01:24:36 Z jamezzz Torrent (COI16_torrent) C++17
100 / 100
 135 ms 29972 KB 
#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,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);
}

Compilation message

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);
      |             ^

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7360 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 22588 KB Output is correct
2 Correct 135 ms 27628 KB Output is correct
3 Correct 126 ms 29380 KB Output is correct
4 Correct 125 ms 28660 KB Output is correct
5 Correct 117 ms 26816 KB Output is correct
6 Correct 127 ms 27332 KB Output is correct
7 Correct 132 ms 29972 KB Output is correct