oj.uz

Submission #80949

# Submission time Handle Problem Language Result Execution time Memory
80949 2018-10-23T08:12:15 Z farukkastamonuda Torrent (COI16_torrent) C++14
100 / 100
 630 ms 51328 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define li 300005
#define mp make_pair
#define pb push_back
using namespace std;
int n, a, b, x, y, tut;
vector<int> v[li], tr, all;
pair<int, int> temp;
void process(){
	for(int i = 0; i < (int)tr.size(); i ++){
		all.pb(tr[i]);
	}
}
void dfs1(int node, int ata){
	tr.pb(node);
	if(node == b){
		process();
		return ;
	}
	for(int i = 0; i < (int)v[node].size(); i ++){
		int go = v[node][i];
		if(go == ata) continue;
		dfs1(go, node);
	}
	tr.pop_back();
}
int dfs(int node, int ata, int durum){
	vector<int> res;
	for(int i = 0; i < (int)v[node].size(); i ++){
		int go = v[node][i];
		if(go == ata || (durum == 0 && go == all[tut + 1])) continue;
		if(durum == 1 && go == all[tut]) continue;
		res.pb(dfs(go, node, durum));
	}
	sort(res.begin(), res.end(), greater<int>());
	int sure=0;
	for(int i = 0 ; i < (int)res.size(); i ++){
		int go = res[i];
		sure=max(sure, go + i + 1);
	}
	return sure;
}
pair< int, int > solve(int val){
	tut = val;
	return mp(dfs(a, 0, 0), dfs(b, 0, 1));
}
int main(){
	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 ans = 1000 * 1000 * 1000;
	int bas = 0, son = (int)all.size() - 2;
	while(bas <= son){
		int mid = (bas + son) / 2;
		temp = solve(mid);
		ans = min(ans, max(temp.fi, temp.se));
		if(temp.fi <= temp.se) bas = mid + 1;
		else son = mid - 1;
	}
	temp = solve(max(son,0));
	ans = min(ans, max(temp.fi, temp.se));
	printf("%d\n", ans);
	return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:53: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:55: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 7548 KB Output is correct
2 Correct 9 ms 7680 KB Output is correct
3 Correct 9 ms 7816 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 23588 KB Output is correct
2 Correct 481 ms 29028 KB Output is correct
3 Correct 444 ms 34384 KB Output is correct
4 Correct 547 ms 38012 KB Output is correct
5 Correct 630 ms 39508 KB Output is correct
6 Correct 479 ms 44384 KB Output is correct
7 Correct 452 ms 51328 KB Output is correct