oj.uz

Submission #865210

# Submission time Handle Problem Language Result Execution time Memory
865210 2023-10-24T06:32:34 Z hehege Torrent (COI16_torrent) C++17
0 / 100
 458 ms 23756 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define pp pair <int, int>
#define mp make_pair
 
const int N = 3e5 + 9;
 
int n, m, s1, s2;
vector <int> adj[N];
 
namespace sub2 {
	int trace[N];
	int cnt[N], res[2][N];
	vector <pp> path2;
	
	bool cmp (int A, int B){
		return cnt[A] > cnt[B];
	}
	
	void dfs1 (int u, int p){
		cnt[u] = 1;
		for (int i : adj[u]) if (i != p){
			dfs1 (i, u); 
			cnt[u] += cnt[i];
		}
		sort (adj[u].begin (), adj[u].end (), cmp);
	}
	
	void dfs2 (int type, int u, int p, int id){
		res[type][u] = id;
		int susge = 0;
		for (int i : adj[u]) if (i != p){
			susge++;
			dfs2 (type, i, u, id + susge);
		}
	}
	
	void dfs (int u, int p){
		trace[u] = p;
		if (u == s2) return;
		for (int i : adj[u]) if (i != p) dfs (i, u);
	}
	
	void del (int u, int v){
		vector <int> vec = adj[u];
		adj[u].clear ();
		for (int i : vec) if (i != v) adj[u].emplace_back (i);
		vec = adj[v];
		adj[v].clear ();
		for (int i : vec) if (i != u) adj[v].emplace_back (i);
	}
	
	void add (int u, int v){
		adj[u].emplace_back (v);
		adj[v].emplace_back (u);
	}
	
	pp get (int val){
		memset (cnt, 0, sizeof (cnt));
		memset (res, 0, sizeof (res));
		del (path2[val].first, path2[val].second);
		dfs1 (s1, s1);
		dfs1 (s2, s2);
		dfs2 (0, s1, s1, 0);
		dfs2 (1, s2, s2, 0);
		int v1 = 0, v2 = 0;
		for (int i = 1; i <= n; i++){
			v1 = max (v1, res[0][i]);
			v2 = max (v2, res[1][i]);
		}
		add (path2[val].first, path2[val].second);
		return mp (v1, v2);
	}
	
	void solve (){
		dfs (s1, -1);
		vector <int> path;
		int cc = s2;
		while (cc != -1){
			path.emplace_back (cc);
			cc = trace[cc];
		}
		for (int i = 0; i + 1 < path.size (); i++) path2.emplace_back (mp (path[i], path[i + 1]));
		int finalres = N + N + N + N;
		int l = 0, r = path2.size (); r--;
		while (l <= r){
			int mid = l + r >> 1;
			pp p = get (mid);
			finalres = min (finalres, max (p.first, p.second));
			if (p.first > p.second) l = mid + 1;
			else r = mid - 1;
		}
		cout << finalres;
	}
}
 
signed main (){
	ios_base::sync_with_stdio (false);
	cin.tie (NULL);
	cout.tie (NULL);
	cin >> n >> s1 >> s2;
	for (int i = 1, u, v; i < n; i++){
		cin >> u >> v;
		adj[u].emplace_back (v);
		adj[v].emplace_back (u);
	}
	sub2::solve ();
}

Compilation message

torrent.cpp: In function 'void sub2::solve()':
torrent.cpp:84:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 0; i + 1 < path.size (); i++) path2.emplace_back (mp (path[i], path[i + 1]));
      |                   ~~~~~~^~~~~~~~~~~~~~
torrent.cpp:88:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |    int mid = l + r >> 1;
      |              ~~^~~

Subtask #1
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 12124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 69.0

# Verdict Execution time Memory Grader output
1 Incorrect 458 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -