oj.uz

Submission #763912

# Submission time Handle Problem Language Result Execution time Memory
763912 2023-06-23T03:11:09 Z siewjh Torrent (COI16_torrent) C++17
100 / 100
 273 ms 38100 KB 
#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));
	}
	sort(nchd.begin(), nchd.end(), greater<int>());
	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

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:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = 0; i < nchd.size(); i++) mxd = max(mxd, i + 1 + nchd[i]);
      |                  ~~^~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:73:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |  cout << ans;
      |          ^~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 8 ms 15956 KB Output is correct
3 Correct 9 ms 15848 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 33632 KB Output is correct
2 Correct 235 ms 35404 KB Output is correct
3 Correct 184 ms 34904 KB Output is correct
4 Correct 273 ms 38100 KB Output is correct
5 Correct 228 ms 33588 KB Output is correct
6 Correct 147 ms 33836 KB Output is correct
7 Correct 168 ms 35980 KB Output is correct