oj.uz

Submission #860818

# Submission time Handle Problem Language Result Execution time Memory
860818 2023-10-14T12:08:58 Z serifefedartar Torrent (COI16_torrent) C++17
100 / 100
 314 ms 26532 KB 
#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";
}

Compilation message

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.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 19284 KB Output is correct
2 Correct 264 ms 24624 KB Output is correct
3 Correct 258 ms 26196 KB Output is correct
4 Correct 314 ms 25592 KB Output is correct
5 Correct 266 ms 22868 KB Output is correct
6 Correct 253 ms 23376 KB Output is correct
7 Correct 272 ms 26532 KB Output is correct