oj.uz

Submission #76485

# Submission time Handle Problem Language Result Execution time Memory
76485 2018-09-13T15:23:57 Z hamzqq9 Torrent (COI16_torrent) C++14
100 / 100
 680 ms 25640 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 60000000000000000
#define MOD 1000000009
#define N 300005
#define MAX 5032117	
#define LOG 30
#define KOK 333
using namespace std;

int tut,n,a,b,x,y;
vector<int> tr,alle,v[N];

int dfs(int node,int ata,bool state) {

	vector<int> ress;

	for(int to:v[node]) {

		if(to==ata || (!state && to==alle[tut+1]) || (state && to==alle[tut])) continue ;

		int res=dfs(to,node,state);

		ress.pb(res);

	}

	sort(all(ress),greater<int>());

	int ret=0;

	for(int i=0;i<sz(ress);i++) umax(ret,ress[i]+i+1);

	return ret;

}

ii solve(int upto) {

	tut=upto;

	return {dfs(a,0,0),dfs(b,0,1)};

}

void process() {

	for(int i:tr) alle.pb(i);

}

void dfs1(int node,int ata) {

	tr.pb(node);

	if(node==b) {

		process();

		return ;

	} 

	for(int i:v[node]) {

		if(i==ata) continue ;

		dfs1(i,node);

	}

	tr.ppb();

}

int main() {

	//freopen("input.txt","r",stdin);

	scanf("%d %d %d",&n,&a,&b);

	for(int i=1;i<n;i++) {

		scanf("%d %d",&x,&y);

		v[x].pb(y);
		v[y].pb(x);

	}

	dfs1(a,0);

	int bas=0,son=sz(alle)-2;
	int ans=10000000;

	while(bas<=son) {

		ii res=solve(orta);

		umin(ans,max(res.st,res.nd));

		if(res.st<=res.nd) bas=orta+1;
		else son=orta-1;

	}

	ii res=solve(max(son,0));

	printf("%d",min(ans,max(res.st,res.nd)));

}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
torrent.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7420 KB Output is correct
2 Correct 9 ms 7420 KB Output is correct
3 Correct 9 ms 7496 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 19416 KB Output is correct
2 Correct 680 ms 23648 KB Output is correct
3 Correct 599 ms 25280 KB Output is correct
4 Correct 631 ms 25280 KB Output is correct
5 Correct 570 ms 25280 KB Output is correct
6 Correct 679 ms 25280 KB Output is correct
7 Correct 563 ms 25640 KB Output is correct