| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 999135 |
2024-06-15T07:13:49 Z |
vjudge1 |
LOSTIKS (INOI20_lostiks) |
C++17 |
|
1823 ms |
132284 KB |
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1e6 + 5, lg = 22;
vector<pair<ll, ll>> g[N];
ll need[N], comp[N], depth[N], up[lg][N];
ll vals[lg], dp[1 << lg][lg];
ll freq[lg][N];
void dfs(ll v, ll par = 0)
{
up[0][v] = par;
for (ll i = 1; i < lg; i++)
up[i][v] = up[i - 1][up[i - 1][v]];
for (auto [to, w] : g[v])
if (to != par)
{
for (ll i = 0; i < lg; i++)
freq[i][to] = freq[i][v];
if (w)
freq[comp[w]][to]++;
depth[to] = depth[v] + 1;
dfs(to, v);
}
}
ll lca(ll a, ll b)
{
if (depth[a] < depth[b])
swap(a, b);
for (ll bit = lg - 1; bit >= 0; bit--)
if (depth[a] - (1 << bit) >= depth[b])
a = up[bit][a];
if (a == b)
return a;
for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][a] != up[bit][b]) a = up[bit][a], b = up[bit][b];
return up[0][a];
}
ll dist(ll a, ll b)
{
return depth[a] + depth[b] - depth[lca(a, b)] * 2;
}
ll needs(ll a, ll b)
{
ll lc = lca(a, b), ans = 0;
for (ll i = 0; i < lg; i++)
if (freq[i][a] + freq[i][b] - freq[i][lc] * 2)
ans |= 1 << i;
return ans;
}
void solve()
{
ll n;
cin >> n;
ll s, t;
cin >> s >> t;
array<ll, 3> e[n - 1];
for (ll i = 0; i < n - 1; i++)
{
cin >> e[i][0] >> e[i][1] >> e[i][2];
g[e[i][0]].push_back(make_pair(e[i][1], e[i][2]));
g[e[i][1]].push_back(make_pair(e[i][0], e[i][2]));
}
ll sz = 0;
{
set<ll> tmp;
for (ll i = 1; i <= n; i++)
for (auto [j, w] : g[i])
if (w)
tmp.insert(w);
tmp.insert(s);
tmp.insert(t);
for (ll i : tmp) comp[i] = sz, vals[sz++] = i;
}
dfs(s, s);
// for (ll i = 0; i < (1 << sz); i++)
// for (ll j = 0; j < sz; j++)
// dp[i][j] = 1e18;
// dp[1 << comp[s]][comp[s]] = 0;
// for (ll msk = 0; msk < (1 << sz); msk++) if (msk != (1 << comp[s]))
// {
// for (ll i = 0; i < sz; i++)
// if (msk >> i & 1)
// for (ll j = 0, x; j < sz; j++)
// {
// x = needs(vals[i], vals[j]);
// if ((msk >> j & 1) and j != i and ((msk ^ (1 << i)) & x) == x)
// dp[msk][i] = min(dp[msk][i], dp[msk ^ (1 << i)][j] + dist(vals[i], vals[j]));
// }
// }
// ll ans = 1e18;
// for (ll msk = 0; msk < (1 << sz); msk++)
// ans = min(ans, dp[msk][comp[t]]);
// if (ans == 1e18)
// ans = -1;
// cout << ans << endl;
ll ans = 1e18;
do
{
if (vals[0] != s or vals[sz - 1] != t)
continue;
ll cur = 1 << comp[vals[0]], res = 0;
bool ok = true;
for (ll i = 1, x; i < sz; i++)
{
x = needs(vals[i], vals[i - 1]);
if ((cur & x) != x)
{
ok = false;
break;
}
res += dist(vals[i], vals[i - 1]);
cur |= 1 << comp[vals[i]];
}
if (ok)
ans = min(ans, res);
} while (next_permutation(vals, vals + sz));
if (ans == 1e18)
ans = -1;
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t = 1;
// precomp();
// cin >> t;
for (ll cs = 1; cs <= t; cs++)
solve();
// cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
71512 KB |
Output is correct |
| 2 |
Correct |
9 ms |
71672 KB |
Output is correct |
| 3 |
Incorrect |
76 ms |
132284 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
71512 KB |
Output is correct |
| 2 |
Correct |
9 ms |
71512 KB |
Output is correct |
| 3 |
Incorrect |
1823 ms |
71772 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
71512 KB |
Output is correct |
| 2 |
Correct |
9 ms |
71672 KB |
Output is correct |
| 3 |
Incorrect |
76 ms |
132284 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
