#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pii array<int,2>
struct tmp {
int node;
bool onl;
int tNeeded;
bool operator<(const tmp &x) {
if (tNeeded != x.tNeeded) {
return tNeeded > x.tNeeded;
}
return onl;
}
};
signed main() {
int n,a,b;cin>>n>>a>>b;a--;b--;
vector<vector<int>> g(n);
for (int i=1;i<n;i++) {
int c,d;cin>>c>>d;c--;d--;
g[c].push_back(d);
g[d].push_back(c);
}
vector<vector<int>> child(n);
vector<int> p(n,-1);
function<void(int,int)> dfs=[&](int node,int pv) {
for (int x:g[node]) {
if (x==pv)continue;
child[node].push_back(x);
p[x]=node;
dfs(x,node);
}
};
dfs(a,-1);
vector<bool> online(n, false);
int pt=b;
while (pt != a) {
online[pt]=true;
pt=p[pt];
}
online[a]=true;
vector<int> times(n, 0);
function<void(int)> dfs2=[&](int node) {
vector<int> vls;
for (int x:child[node]) {
dfs2(x);
if (!online[x]) {
vls.push_back(times[x]);
}
}
sort(vls.begin(),vls.end(),greater<int>());
for (int i=0;i<vls.size();i++) {
times[node]=max(times[node], vls[i] + i + 1);
}
};
dfs2(a);
vector<bool> marked(n, false);
vector<int> ntime(n, 1e9);
// priority queue: {time, node}
priority_queue<pii, vector<pii>> pq;
pq.push({0, a});
pq.push({0, b});
ntime[a] = ntime[b] = 0;
while (!pq.empty()) {
auto [t, nd]=pq.top();pq.pop();
if (marked[nd])continue;
marked[nd] = true;
ntime[nd] = -t;
vector<tmp> vls;
for (auto &x:g[nd]) {
tmp tt;
tt.onl = online[x];
tt.tNeeded = times[x];
tt.node = x;
vls.push_back(tt);
}
sort(vls.begin(), vls.end());
int startTime = -t + 1;
for (int i=0;i<vls.size();i++) {
if (ntime[vls[i].node] > startTime) {
ntime[vls[i].node] = startTime;
pq.push({-startTime, vls[i].node});
startTime++;
}
}
}
int mx=0;
for (int x:ntime) {
// cout<<x<<" ";
mx = max(mx, x);
}
// cout<<"\n";
cout<<mx<<"\n";
}
Compilation message
torrent.cpp: In lambda function:
torrent.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i=0;i<vls.size();i++) {
| ~^~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:78:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
78 | auto [t, nd]=pq.top();pq.pop();
| ^
torrent.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<tmp>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int i=0;i<vls.size();i++) {
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
323 ms |
44712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
