oj.uz

답안 #199066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199066 2020-01-29T04:18:44 Z kshitij_sodani Torrent (COI16_torrent) C++17
100 / 100
 839 ms 29940 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int llo;
#define mp make_pair
#define pb push_back

vector<llo> st;
vector<llo> path;
llo a,b,c,d;
vector<llo> adj[300010];
llo vis[300010];
void dfs(llo no){
	if(no==b-1){
		for(llo i=0;i<st.size();i++){
			path.pb(st[i]);
		}

	}
	for(llo j=0;j<adj[no].size();j++){
		llo nn=adj[no][j];
		if(vis[nn]==1){
			continue;
		}
		st.pb(nn);
		vis[nn]=1;
		dfs(nn);
		st.pop_back();
	}
}
llo dfs2(llo no){
//	cout<<no<<" ";
	vector<llo> pp;
	for(llo j=0;j<adj[no].size();j++){
		llo nn=adj[no][j];
		if(vis[nn]==0){
			if((no==c and nn==d) or (no==d and nn==c)){
				continue;
			}
			vis[nn]=1;
			pp.pb(dfs2(nn));
		}
	}
	if(pp.size()==0){
		return 0;
	}
	sort(pp.begin(),pp.end());
	llo ma=0;
	/*if(no==a-1){
		for(llo i=0;i<pp.size();i++){
			cout<<pp[i]<<" ";
		}
		cout<<endl;
	}*/
	for(llo i=0;i<pp.size();i++){
		ma=max(ma,(i+1)+pp[pp.size()-1-i]);
	}
	return ma;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n;
	cin>>n>>a>>b;
	llo x,y;
	for(llo i=0;i<n-1;i++){
		cin>>x>>y;
		adj[x-1].pb(y-1);
		adj[y-1].pb(x-1);
	}
	st.pb(a-1);
	memset(vis,0,sizeof(vis));
	dfs(a-1);
	llo low=0;
	llo high=path.size()-2;
	/*for(llo i=0;i<path.size();i++){
		cout<<path[i]<<" ";
	}
	cout<<endl;*/
	while(low<high-1){
		llo mid=(low+high)/2;
		memset(vis,0,sizeof(vis));
		c=path[mid];
		d=path[mid+1];
		vis[a-1]=1;
		vis[b-1]=1;
		llo aa=dfs2(a-1);
		llo bb=dfs2(b-1);
		if(aa<bb){
			low=mid;
		}
		else{
			high=mid;
		}
	}
	llo ma=4000000;
	for(llo j=low;j<high+1;j++){
		memset(vis,0,sizeof(vis));	
		c=path[j];
		d=path[j+1];
		vis[a-1]=1;
		llo aa=dfs2(a-1);
	//	cout<<endl;
		vis[b-1]=1;
		llo bb=dfs2(b-1);
	//	cout<<endl;
	//	cout<<aa<<":"<<bb<<endl;
		ma=min(ma,max(aa,bb));
	//	cout<<max(aa,bb)<<endl;
	}
	cout<<ma<<endl;
	

	return 0;
}

Compilation message

torrent.cpp: In function 'void dfs(llo)':
torrent.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(llo i=0;i<st.size();i++){
               ~^~~~~~~~~~
torrent.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo j=0;j<adj[no].size();j++){
              ~^~~~~~~~~~~~~~~
torrent.cpp: In function 'llo dfs2(llo)':
torrent.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo j=0;j<adj[no].size();j++){
              ~^~~~~~~~~~~~~~~
torrent.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(llo i=0;i<pp.size();i++){
              ~^~~~~~~~~~

Subtask #1
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 9720 KB Output is correct
2 Correct 13 ms 9720 KB Output is correct
3 Correct 13 ms 9720 KB Output is correct

Subtask #2
69.0 / 69.0

# 결과 실행 시간 메모리 Grader output
1 Correct 613 ms 27140 KB Output is correct
2 Correct 678 ms 28100 KB Output is correct
3 Correct 839 ms 29276 KB Output is correct
4 Correct 643 ms 28656 KB Output is correct
5 Correct 730 ms 26360 KB Output is correct
6 Correct 551 ms 27076 KB Output is correct
7 Correct 547 ms 29940 KB Output is correct