Submission #1104717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104717		PieArmy	Torrent (COI16_torrent)	C++17	100 / 100	379 ms	28520 KiB

torrent

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n,a,b;
vector<pair<int,int>>komsu[300001];
vector<int>edges;

int solve(int pos,int par,int yasak){
	int res=0;
	vector<int>v;
	for(auto x:komsu[pos]){
		if(x.fr==par)continue;
		if(x.sc==yasak)continue;
		v.pb(solve(x.fr,pos,yasak));
	}
	sort(v.begin(),v.end());
	int m=v.size();
	for(int i=0;i<m;i++){
		res=max(res,v[i]+m-i);
	}
	return res;
}
bool dfs(int pos,int par){
	if(pos==b)return true;
	bool res=false;
	for(auto x:komsu[pos]){
		if(x.fr==par)continue;
		if(dfs(x.fr,pos)){
			res=true;
			edges.pb(x.sc);
		}
	}
	return res;
}

void code(){
	cin>>n>>a>>b;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb({y,i});
		komsu[y].pb({x,i});
	}
	dfs(a,a);
	int l=0,r=edges.size()-1;
	while(l<r-1){
		int m=(l+r)/2;
		int resa=solve(a,a,edges[m]),resb=solve(b,b,edges[m]);
		if(resb>resa){
			r=m;
		}
		else l=m;
	}
	cout<<min(max(solve(a,a,edges[l]),solve(b,b,edges[l])),max(solve(a,a,edges[r]),solve(b,b,edges[r])));
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
	int t=1;
	if(!t)cin>>t;
	while(t--){code();cout<<endl;}
	return 0;
}

Compilation message (stderr)

torrent.cpp: In function 'int main()':
torrent.cpp:68:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~
torrent.cpp:68:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69