| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 501289 |
2022-01-02T18:18:34 Z |
aryan12 |
Torrent (COI16_torrent) |
C++17 |
|
146 ms |
34024 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 5;
vector<int> g[N];
int minNum[N];
int tin[N], tout[N], tim = 0;
int n, a, b;
vector<pair<int, int> > values(N); //for nodes between A->B
int max1 = 0, max2 = 0, max3 = 0;
void dfsTime(int node, int par) {
tin[node] = ++tim;
for(int i = 0; i < g[node].size(); i++) {
if(g[node][i] != par) {
dfsTime(g[node][i], node);
}
}
tout[node] = ++tim;
}
void dfs(int node, int par) {
//cout << "node = " << node << "\n";
minNum[node] = 0; //min turns to colour the subtree of this node
vector<int> childDp;
for(int i = 0; i < g[node].size(); i++) {
if(g[node][i] == par) {
continue;
}
//cout << "node = " << node <<", g[node][i] = " << g[node][i] << "\n";
dfs(g[node][i], node);
childDp.push_back(minNum[g[node][i]]);
}
if(childDp.size() == 0) {
return;
}
sort(childDp.begin(), childDp.end());
int ans = 0, cnt = 0;
for(int i = childDp.size() - 1; i >= 0; i--) {
ans = max(ans, childDp[i] + ++cnt);
}
minNum[node] = ans;
}
void DfsB(int node, int par) {
//cout << "DfsB -- node = " << node << ", par = " << par << "\n";
values[node].second = 0;
vector<int> children;
for(int i = 0; i < g[node].size(); i++) {
if(g[node][i] == par || g[node][i] == a) {
continue;
}
if(node == b && tin[g[node][i]] > tin[node]) {
continue;
}
DfsB(g[node][i], node);
children.push_back(values[g[node][i]].second);
}
sort(children.begin(), children.end());
reverse(children.begin(), children.end());
int ans = 0;
for(int i = 0; i < children.size(); i++) {
ans = max(ans, children[i] + i + 1);
}
values[node].second = ans;
max2 = max(max2, ans);
}
void DfsA(int node, int par) {
//cout << "DfsA -- node = " << node << ", par = " << par << "\n";
values[node].first = 0;
vector<int> children;
for(int i = 0; i < g[node].size(); i++) {
if(g[node][i] == par || g[node][i] == b || tin[g[node][i]] > tout[b]) {
continue;
}
DfsA(g[node][i], node);
children.push_back(values[g[node][i]].first);
}
sort(children.begin(), children.end());
reverse(children.begin(), children.end());
int ans = 0;
for(int i = 0; i < children.size(); i++) {
ans = max(ans, children[i] + i + 1);
}
values[node].first = ans;
max1 = max(max1, ans);
}
void Solve() {
cin >> n >> a >> b;
//cout << "a = " << a << ", b = " << b << "\n";
bool f1 = false;
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
if((u == a && v == b) || (u == b || v == a)) {
f1 = true;
}
g[u].push_back(v);
g[v].push_back(u);
}
dfsTime(a, -1);
dfs(a, -1); //only calculate from A to other nodes
int minans = 0; //all other subtrees from A except the one which contains B
vector<int> childVal;
for(int i = 0; i < g[a].size(); i++) {
if(tin[g[a][i]] <= tin[b] && tout[g[a][i]] >= tout[b]) {
continue;
}
childVal.push_back(minNum[g[a][i]]);
}
sort(childVal.begin(), childVal.end());
reverse(childVal.begin(), childVal.end());
for(int i = 0; i < childVal.size(); i++) {
minans = max(minans, childVal[i] + i + 1);
}
int minansforB = minNum[b];
//cout << "minans = " << minans << ", minansforB = " << minansforB << "\n";
/*for(int i = 1; i <= n; i++) {
cout << "i = " << i << ", minNum[i] = " << minNum[i] << "\n";
}
cout << "\n";*/
//only thing left - cover the gap between a and b -- might be a whole subtree!
DfsB(b, -1);
DfsA(a, -1);
for(int i = 1; i <= n; i++) {
if(values[i].first != 0 || values[i].second != 0) {
max3 = max(max3, min(values[i].first, values[i].second));
}
}
//max3 = min(max1, max2);
int finalans = INT_MAX;
if(f1) finalans = min(finalans, max({minans, minansforB}));
finalans = min(finalans, max({minans + 1, minansforB, max1}));
finalans = min(finalans, max({minans, minansforB + 1, max2}));
finalans = min(finalans, max({minans + 1, minansforB + 1, max3}));
cout << finalans << "\n";
}
int32_t main() {
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Compilation message
torrent.cpp: In function 'void dfsTime(long long int, long long int)':
torrent.cpp:17:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i = 0; i < g[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
torrent.cpp: In function 'void dfs(long long int, long long int)':
torrent.cpp:29:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i = 0; i < g[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
torrent.cpp: In function 'void DfsB(long long int, long long int)':
torrent.cpp:52:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i < g[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
torrent.cpp:65:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i = 0; i < children.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
torrent.cpp: In function 'void DfsA(long long int, long long int)':
torrent.cpp:76:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < g[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
torrent.cpp:86:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 0; i < children.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
torrent.cpp: In function 'void Solve()':
torrent.cpp:111:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for(int i = 0; i < g[a].size(); i++) {
| ~~^~~~~~~~~~~~~
torrent.cpp:119:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i = 0; i < childVal.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
146 ms |
34024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
