제출 #860818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
860818		serifefedartar	Torrent (COI16_torrent)	C++17	100 / 100	314 ms	26532 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18; 
const ll MAXN = 3e5 + 100;

vector<vector<int>> graph;
int a, b;
vector<int> path;

bool control = false;
void dfs(int node, int parent) {
	path.push_back(node);
	if (node == b)
		control = true;

	for (auto u : graph[node]) {
		if (u == parent || control)
			continue;
		dfs(u, node);
	}

	if (!control)
		path.pop_back();
}

int time(int node, int parent, int not_go) {
	vector<int> t;
	for (auto u : graph[node]) {
		if (u == parent || u == not_go)
			continue;
		t.push_back(time(u, node, not_go));
	}
	sort(t.begin(), t.end(), greater<int>());
	
	int mx = 0;
	for (int i = 0; i < t.size(); i++)
		mx = max(mx, t[i] + i + 1);
	return mx;
}

pair<bool,int> check(int x) {
	int t1 = time(a, a, path[x]);
	int t2 = time(b, b, path[x-1]);
	return {t2 > t1, max(t1, t2)};
}

int main() {
	fast
	int n, u, v;
	cin >> n >> a >> b;

	graph = vector<vector<int>>(n+1, vector<int>());
	for (int i = 1; i < n; i++) {
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	dfs(a, a);

	int L = 1;
	int R = path.size() - 1;
	int ans = R;
	while (R >= L) {
		int mid = L + (R-L)/2;
		if (check(mid).f) {
			ans = mid;
			L = mid + 1;
		} else
			R = mid - 1;
	}

	int q = check(ans).s;
	if (ans != path.size() - 1)
		q = min(q, check(ans+1).s);
	cout << q << "\n";
}

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

torrent.cpp: In function 'int time(int, int, int)':
torrent.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for (int i = 0; i < t.size(); i++)
      |                  ~~^~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:79:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  if (ans != path.size() - 1)
      |      ~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 31 / 31
• Subtask 2: 69 / 69