/// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
#define Fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define RFOR(i,a) for(int i = a-1; i >= 0; i--)
#define FOR(i,a) for(int i = 0; i < a; i++)
#define se second
#define fi first
#define sz(x) (int)x.size()
#define upp upper_bound
#define low lower_bound
#define pub push_back
#define all(x) x.begin(),x.end()
#define mp make_pair
typedef double ld;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int N = 1'000'000 + 5;
int H[N];
pii dad[N];
vector<pii> G[N];
int n, s, t;
vector<int> way; /// better
bitset<N> L, UL;
void dfs(int v, int h, pii d)
{
dad[v] = d;
H[v] = h;
for(auto u: G[v])if(u.fi != d.fi)dfs(u.fi,h+1,mp(v,u.se));
}
vector<int> f(int st, int en)
{
cout << st << ' ' << en << endl;
vector<pii> inv;
vector<int> road, ex;
if(H[st] < H[en])
{
while(H[st] < H[en])
{
inv.pub(mp(en,dad[en].se));
en = dad[en].fi;
}
}
if(H[st] > H[en])
{
while(H[st] > H[en])
{
if(dad[st].se && !UL[st])
{
if(L[dad[st].fi]){cout << -1;exit(0);}
L[dad[st].fi] = true;
ex = f(st,dad[st].se);
for(auto u: ex)road.pub(u);
for(int i = sz(ex)-3; i; i--)road.pub(ex[i]);
UL[st] = true;
}
road.pub(st);
st = dad[st].fi;
}
}
while(st != en)
{
inv.pub(dad[en]);
en = dad[en].fi;
if(dad[st].se && !UL[st])
{
if(L[dad[st].fi]){cout << -1;exit(0);}
L[dad[st].fi] = true;
ex = f(st,dad[st].se);
for(auto u: ex)road.pub(u);
for(int i = sz(ex)-3; i; i--)road.pub(ex[i]);
UL[st] = true;
}
road.pub(st);
st = dad[st].fi;
}
road.pub(st);
for(int i = sz(inv)-1; i >= 0; i--)
{
if(inv[i].se && !UL[inv[i].fi])
{
if(L[inv[i].fi]){cout << -1;exit(0);}
L[inv[i].fi] = true;
ex = f(road.back(),inv[i].se);
for(auto u: ex)road.pub(u);
for(int i = sz(ex)-3; i >= 0; i--)road.pub(ex[i]);
UL[inv[i].fi] = true;
}
road.pub(inv[i].fi);
}
road.pub(-1);
return road;
}
inline void optimize(vector<int> &A)
{
if(sz(A) < 3)return;
vector<int> B;
for(int i = 0; i < sz(A); i++)
{
while((A[i] != -1 && sz(B) >= 2 && A[i] == B[sz(B)-2]))
{
B.pop_back();
B.pop_back();
}
while(!B.empty() && B.back() == A[i])B.pop_back();
B.pub(A[i]);
//for(auto y: B)cout << y << ' ';
//cout << '\n';
}
A.swap(B);
}
int main()
{
Fast
/// 1-base-code
/// khod kelidi
cin >> n >> s >> t;
int u, v, k;
FOR(i,n-1)
{
cin >> u >> v >> k;
G[u].pub(mp(v,k));
G[v].pub(mp(u,k));
}
dfs(1,0,mp(-1,-1));
way = f(s,t);
//for(auto u: way)cout << u << ' ';
//cout << '\n';
optimize(way);
//for(auto u: way)cout << u << ' ';
//cout << '\n';
int ans = -1;
for(auto u: way)if(u != -1)ans++;
cout << ans;
return 0;
}
// thank god
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
