Submission #865142

#	Time	Username	Problem	Language	Result	Execution time	Memory
865142		hehege	Torrent (COI16_torrent)	C++14	0 / 100	22 ms	13404 KiB

torrent

#include <bits/stdc++.h>
using namespace std;

#define pp pair <int, int>
#define mp make_pair

const int N = 1e5 + 9;

int n, m, s1, s2;
vector <int> adj[N];

namespace sub1 {
	int cnt[N], res[N];
	
	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 u, int p, int id){
		res[u] = id;
		int susge = 0;
		for (int i : adj[u]) if (i != p){
			susge++;
			dfs2 (i, u, id + susge);
		}
	}
	
	void solve (){
		int s1; cin >> s1;
		dfs1 (s1, s1);
		dfs2 (s1, s1, 0);
		int finalres = 0;
		for (int i = 1; i <= n; i++) finalres = max (finalres, res[i]);
		cout << finalres;
	}
}

namespace sub2 {
	//int s1, s2;
	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 (){
		//cin >> s1 >> s2;
		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);
	if (fopen ("TDL.INP", "r")){
		freopen ("TDL.INP", "r", stdin);
		freopen ("TDL.OUT", "w", stdout);
	}
	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);
	}
	m=2;
	if (m == 1) sub1::solve ();
	else sub2::solve ();
}

Compilation message (stderr)

torrent.cpp: In function 'void sub2::solve()':
torrent.cpp:121:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for (int i = 0; i + 1 < path.size (); i++) path2.emplace_back (mp (path[i], path[i + 1]));
      |                   ~~~~~~^~~~~~~~~~~~~~
torrent.cpp:125:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |    int mid = l + r >> 1;
      |              ~~^~~
torrent.cpp: In function 'int main()':
torrent.cpp:140:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |   freopen ("TDL.INP", "r", stdin);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:141:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   freopen ("TDL.OUT", "w", stdout);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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