| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 76400 |
2018-09-13T12:41:51 Z |
mfbalin |
Torrent (COI16_torrent) |
C++17 |
|
1049 ms |
19588 KB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, a, b;
vector<vector<int>> g;
bool dfs(int s, vector<int> &v, int p = -1) {
if(s == ::b)
return true;
v.push_back(s);
bool b = false;
for(auto i: g[s])
if(i != p) {
b = dfs(i, v, s);
if(b)
break;
}
if(!b)
v.pop_back();
return b;
}
int solve(int s, int p = -1) {
vector<int> t(1, 0);
for(auto i: g[s])
if(i != p)
t.push_back(solve(i, s));
sort(t.begin(), t.end());
int ans = t.back();
for(int i = t.size() - 2; i >= 0; i--)
if(t[i] == t[i + 1])
ans++;
return ans + 1;
}
int main(int argc, char *argv[]) {
ios::sync_with_stdio(false);
cin >> N >> a >> b;
a--; b--;
g.resize(N);
for(int i = 1; i < N; i++) {
int a, b;
cin >> a >> b;
a--; b--;
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> v;
dfs(a, v);
int l = 0, r = v.size() - 1;
v.push_back(b);
int ans = 1000000;
while(l <= r) {
int m = (l + r) / 2;
g[v[m]].erase(find(g[v[m]].begin(), g[v[m]].end(), v[m + 1]));
g[v[m + 1]].erase(find(g[v[m + 1]].begin(), g[v[m + 1]].end(), v[m]));
int ta = solve(a) - 1;
int tb = solve(b) - 1;
ans = min(ans, max(ta, tb));
//cerr << v[m] + 1 << ' ' << ta << ' ' << tb << endl;
g[v[m]].push_back(v[m + 1]);
g[v[m + 1]].push_back(v[m]);
if(l == r)
break;
if(ta < tb)
l = m + 1;
else
r = m;
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1049 ms |
19588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
