Submission #763897

#	Time	Username	Problem	Language	Result	Execution time	Memory
763897		siewjh	Torrent (COI16_torrent)	C++17	31 / 100	251 ms	42208 KiB

torrent

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
vector<int> adj[MAXN], chd[MAXN];
int sp[MAXN], mxtime[MAXN];
bool cover[MAXN];
int nums, s1, s2; 
bool dfs(int x, int par){
	if (x == s2) return 1;
	for (int nxt : adj[x]){
		if (nxt == par) continue;
		if (dfs(nxt, x)){
			sp[x] = nxt;
			return 1;
		}
	}
	return 0;
}
int dfs2(int x, int par){
	for (int nxt : adj[x]){
		if (nxt == par) continue;
		int currd = dfs2(nxt, x);
		if (nxt != sp[x]) chd[x].push_back(currd);
	}
	sort(chd[x].begin(), chd[x].end(), greater<int>());
	int mxd = 0;
	for (int i = 0; i < chd[x].size(); i++) mxd = max(mxd, i + 1 + chd[x][i]);
	return mxtime[x] = mxd;
}
void dfs3(int x, int par, int tleft){
	if (mxtime[x] > tleft) return;
	if (x == s2) return;
	cover[x] = 1;
	int lastexact = 0;
	for (int i = 0; i < chd[x].size(); i++)
		if (i + 1 + chd[x][i] == tleft)
			lastexact = i + 1;
	dfs3(sp[x], x, tleft - (lastexact + 1));
}
int dfs4(int x, int par){
	vector<int> nchd;
	for (int nxt : adj[x]){
		if (nxt == par || cover[nxt]) continue;
		nchd.push_back(dfs4(nxt, x));
	}
	int mxd = 0;
	for (int i = 0; i < nchd.size(); i++) mxd = max(mxd, i + 1 + nchd[i]);
	return mxd;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> nums >> s1 >> s2;
	for (int i = 1; i < nums; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	memset(sp, -1, sizeof(sp));
	dfs(s1, -1); dfs2(s1, -1);
	int l = 0, r = nums, ans;
	while (l <= r){
		int m = (l + r) >> 1;
		memset(cover, 0, sizeof(cover));
		dfs3(s1, -1, m);
		if (dfs4(s2, -1) <= m){
			ans = m;
			r = m - 1;
		}
		else l = m + 1;
	}
	cout << ans;
}

Compilation message (stderr)

torrent.cpp: In function 'int dfs2(int, int)':
torrent.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0; i < chd[x].size(); i++) mxd = max(mxd, i + 1 + chd[x][i]);
      |                  ~~^~~~~~~~~~~~~~~
torrent.cpp: In function 'void dfs3(int, int, int)':
torrent.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0; i < chd[x].size(); i++)
      |                  ~~^~~~~~~~~~~~~~~
torrent.cpp: In function 'int dfs4(int, int)':
torrent.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i = 0; i < nchd.size(); i++) mxd = max(mxd, i + 1 + nchd[i]);
      |                  ~~^~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:72:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |  cout << ans;
      |          ^~~

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