#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
const int MAXN = 1000100;
const int MAXE = 22;
const int LOGN = 25;
int n, s, t, m;
int ef[MAXN], eto[MAXN], ky[MAXN], kind[MAXN];
vector<int> adj[MAXN];
int lpar[LOGN][MAXN];
int h[MAXN];
int pth[MAXN];
int lck[MAXE];
int dp[1 << 20][MAXE];
int inp[MAXE];
int cost[MAXE][MAXE];
void dfs(int v)
{
for (int e : adj[v])
{
int u = ef[e] ^ eto[e] ^ v;
if (u == lpar[0][v]) continue;
lpar[0][u] = v;
h[u] = h[v] + 1;
pth[u] = pth[v] | (ky[e] ? (1 << kind[e]) : 0);
dfs(u);
}
}
inline int getpar(int x, int d)
{
FOR(i, 0, LOGN) if (d >> i & 1) x = lpar[i][x];
return x;
}
inline int getlca(int x, int y)
{
if (h[x] > h[y]) swap(x, y);
y = getpar(y, h[y] - h[x]);
if (x == y) return x;
for (int i = LOGN - 1; i >= 0; i--)
{
if (lpar[i][x] != lpar[i][y])
{
x = lpar[i][x];
y = lpar[i][y];
}
}
return lpar[0][x];
}
int32_t main(void)
{
fast_io;
cin >> n >> s >> t;
FOR(i, 0, n - 1)
{
cin >> ef[i] >> eto[i] >> ky[i];
adj[ef[i]].pb(i);
adj[eto[i]].pb(i);
if (ky[i])
{
lck[m] = i;
kind[i] = m;
m++;
}
}
dbg(m);
dfs(s);
dbgr(pth + 1, pth + n + 1);
if (pth[t] == 0)
{
return cout << h[t] << endl, 0;
}
FOR(i, 0, n - 1) if (h[ef[i]] > h[eto[i]]) swap(ef[i], eto[i]);
FOR(i, 1, LOGN) FOR(j, 1, n + 1) lpar[i][j] = lpar[i - 1][lpar[i - 1][j]];
FOR(i, 0, m)
{
int e = lck[i];
inp[i] = (pth[ef[e]] | pth[ky[e]]);
}
FOR(i, 0, m) FOR(j, 0, m) if (i != j)
{
int x = ef[lck[i]];
int y = ky[lck[j]];
int z = ef[lck[j]];
cost[i][j] = h[x] + h[y] - 2 * h[getlca(x, y)] + h[y] + h[z] - 2 * h[getlca(y, z)];
// cout << i << ' ' << j << ' ' << cost[i][j] << endl;
}
dbgr(h + 1, h + n + 1);
dbgr(pth + 1, pth + n + 1);
dbgr(lck, lck + m);
dbgr(inp, inp + m);
FOR(mask, 1, 1 << m) fill(dp[mask], dp[mask] + MAXE, INF);
FOR(mask, 1, 1 << m)
{
if (__builtin_popcount(mask) == 1)
{
int v = __lg(mask);
if (!(inp[v] & mask)) dp[mask][v] = 0;
continue;
}
FOR(v, 0, m)
{
if ((mask >> v & 1) && (inp[v] & mask) == 0)
{
int sub = mask ^ (1 << v);
FOR(x, 0, m) if (sub >> x & 1)
{
dp[mask][v] = min(dp[mask][v], dp[sub][x] + cost[v][x]);
}
}
}
}
// FOR(mask, 0, 1 << m) FOR(v, 0, m) cout << v << ' ' << mask << ' ' << dp[mask][v] << endl;
int laste = -1;
FOR(i, 0, m) if (pth[t] >> i & 1) if (laste == -1 || h[ef[lck[i]]] > h[ef[lck[laste]]]) laste = i;
int tot = inp[laste] | (1 << laste);
int ans = INF;
FOR(v, 0, m)
{
int cs = h[ky[lck[v]]] + h[ky[lck[v]]] + h[ef[lck[v]]] - 2 * h[getlca(ky[lck[v]], ef[lck[v]])];
ans = min(ans, cs + dp[tot][v]);
}
if (ans >= INF) return cout << "-1\n", 0;
ans += h[t] - h[ef[lck[laste]]];
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
24004 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24012 KB |
Output is correct |
| 3 |
Correct |
77 ms |
39104 KB |
Output is correct |
| 4 |
Correct |
72 ms |
39184 KB |
Output is correct |
| 5 |
Correct |
71 ms |
39316 KB |
Output is correct |
| 6 |
Correct |
74 ms |
39120 KB |
Output is correct |
| 7 |
Correct |
75 ms |
39228 KB |
Output is correct |
| 8 |
Correct |
81 ms |
39196 KB |
Output is correct |
| 9 |
Correct |
79 ms |
39424 KB |
Output is correct |
| 10 |
Correct |
73 ms |
39196 KB |
Output is correct |
| 11 |
Correct |
76 ms |
39272 KB |
Output is correct |
| 12 |
Incorrect |
68 ms |
41156 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
24052 KB |
Output is correct |
| 2 |
Correct |
15 ms |
24012 KB |
Output is correct |
| 3 |
Correct |
14 ms |
24140 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
24164 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
24004 KB |
Output is correct |
| 2 |
Correct |
13 ms |
24012 KB |
Output is correct |
| 3 |
Correct |
77 ms |
39104 KB |
Output is correct |
| 4 |
Correct |
72 ms |
39184 KB |
Output is correct |
| 5 |
Correct |
71 ms |
39316 KB |
Output is correct |
| 6 |
Correct |
74 ms |
39120 KB |
Output is correct |
| 7 |
Correct |
75 ms |
39228 KB |
Output is correct |
| 8 |
Correct |
81 ms |
39196 KB |
Output is correct |
| 9 |
Correct |
79 ms |
39424 KB |
Output is correct |
| 10 |
Correct |
73 ms |
39196 KB |
Output is correct |
| 11 |
Correct |
76 ms |
39272 KB |
Output is correct |
| 12 |
Incorrect |
68 ms |
41156 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
