oj.uz

Submission #328341

# Submission time Handle Problem Language Result Execution time Memory
328341 2020-11-16T07:24:16 Z M_W Torrent (COI16_torrent) C++14
100 / 100
 966 ms 25448 KB 
#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
vector<int> adj[300300];
bool vis[300300];
int N, A, B;
stack<int> stk;
vector<int> pth;

int findp(int a){
	vis[a] = true;
	if(a == B){
		while(!stk.empty()){
			pth.push_back(stk.top());
			stk.pop();
		}
		return -1;
	}
	for(auto x : adj[a]){
		if(!vis[x]){
			stk.push(x);
			int p = findp(x);
			if(p == -1) return -1;
			stk.pop();
		}
	}
	return 0;
}

int dfs(int a, int u, int v){
	vis[a] = true;
	set<ii> s;
	for(auto x : adj[a])
		if(!vis[x] && !((a == u && x == v) || (a == v && x == u))) s.insert(make_pair(dfs(x, u, v), x));
		
	int ret = 0, ia = s.size();
	for(auto x : s){
		ret = max(ret, x.first + ia);
		ia--;
	}
	return ret;
}

int main(){
	scanf("%d %d %d", &N, &A, &B);
	for(int i = 1, u, v; i < N; i++){
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	findp(A);
	pth.push_back(A);
	int len = pth.size(), mindist = INT_MAX;
	
	int l = 0, r = len - 1;
	while(l < r){
		int mid = (l + r)/2;
		memset(vis, 0, sizeof vis);
		
		int x = dfs(A, pth[mid], pth[mid + 1]);
		int y = dfs(B, pth[mid], pth[mid + 1]);
		
		mindist = min(mindist, max(x, y));
		if(x <= y){
			r = mid;
		}
		else{	
			l = mid + 1;
		}
	}
	
	printf("%d", mindist);
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |  scanf("%d %d %d", &N, &A, &B);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7660 KB Output is correct
2 Correct 8 ms 7660 KB Output is correct
3 Correct 6 ms 7660 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 20332 KB Output is correct
2 Correct 914 ms 22268 KB Output is correct
3 Correct 966 ms 24816 KB Output is correct
4 Correct 930 ms 23660 KB Output is correct
5 Correct 701 ms 19600 KB Output is correct
6 Correct 603 ms 21228 KB Output is correct
7 Correct 568 ms 25448 KB Output is correct