제출 #328312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
328312		M_W	Torrent (COI16_torrent)	C++14	0 / 100	138 ms	40508 KiB

torrent

#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);
			stk.pop();
			if(p == -1) return -1;
		}
	}
	return 0;
}

int dfs(int a, int u, int v){
	vis[a] = true;
	set<ii> s;
	for(auto x : adj[a])
		if(!vis[x] && x != u && x != v) 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);
	memset(vis, 0, sizeof vis);
	int len = pth.size();
	int mindist = max(dfs(A, pth[len - 2], pth[len - 1]), dfs(B, pth[len - 2], pth[len - 1]));
	
	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]);
		
		if(max(x, y) <= mindist){
			r = mid;
		}
		else{
			mindist = max(x, y);
			l = mid + 1;
		}
	}
	printf("%d", mindist);
}

컴파일 시 표준 에러 (stderr) 메시지

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: 0 / 31
• Subtask 2: 0 / 69