oj.uz

Submission #1104717

# Submission time Handle Problem Language Result Execution time Memory
1104717 2024-10-24T09:17:20 Z PieArmy Torrent (COI16_torrent) C++17
100 / 100
 379 ms 28520 KB 
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

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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7504 KB Output is correct
2 Correct 3 ms 7528 KB Output is correct
3 Correct 3 ms 7504 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 24648 KB Output is correct
2 Correct 209 ms 26148 KB Output is correct
3 Correct 228 ms 28004 KB Output is correct
4 Correct 280 ms 26892 KB Output is correct
5 Correct 379 ms 24072 KB Output is correct
6 Correct 272 ms 24924 KB Output is correct
7 Correct 255 ms 28520 KB Output is correct