| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 789121 |
2023-07-21T05:33:35 Z |
MISM06 |
LOSTIKS (INOI20_lostiks) |
C++14 |
|
11 ms |
25172 KB |
//0 1 1 0 1
//0 1 0 0 1
//1 0 0 1 1
//0 1 1 0 1
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2")
using namespace std;
#define F first
#define S second
#define pb push_back
#define sze size()
#define all(x) x.begin() , x.end()
#define wall__ cout << "--------------------------------------\n";
#define kids int mid = (tl + tr) >> 1, cl = v << 1, cr = v << 1 | 1
#define file_io freopen("input.cpp", "r", stdin); freopen("output.cpp", "w", stdout);
typedef long long ll;
typedef long double dl;
typedef pair < int , int > pii;
typedef pair < int , ll > pil;
typedef pair < ll , int > pli;
typedef pair < ll , ll > pll;
typedef pair < int , pii > piii;
typedef pair < ll, pll > plll;
const ll N = (1 << 20) + 10, M = 23;
const ll mod = 1e9 + 7;
const ll inf = 2e16;
const ll INF = 1e9 + 10;
const ll lg = 20;
ll n, s, t, h[N], st[N], en[N], m, timer = 0, par[lg][N], id[N], rid[N];
int inp[M * 2][M * 2];
vector < int > g[N];
piii lc[M];
ll dp[M][N];
void dfs (int v, int p) {
h[v] = h[p] + 1;
st[v] = ++timer;
par[0][v] = p;
for (int i = 1; i < lg; i++) par[i][v] = par[i - 1][par[i - 1][v]];
for (auto u : g[v]) {
if (u == p) continue;
dfs(u, v);
}
en[v] = timer;
}
inline bool be_anc (int v, int u) {
return (st[v] <= st[u] && en[v] >= en[u]);
}
inline int lca (int v, int u) {
if (be_anc(v, u)) return v;
if (be_anc(u, v)) return u;
for (int i = lg - 1; i >= 0; --i) {
if (!be_anc(par[i][v], u)) v = par[i][v];
}
return par[0][v];
}
inline bool is_in_path (int x, int v, int u) {
if (x == v || x == u || x == lca(v, u)) return 1;
if (be_anc(x, v) && !be_anc(x, u)) return 1;
if (be_anc(x, u) && !be_anc(x, v)) return 1;
return 0;
}
inline ll dis (int v, int u) {
return h[v] + h[u] - 2 * h[lca(v, u)];
}
void solve () {
cin >> n >> s >> t;
for (int i = 1; i < n; i++) {
int v, u, w;
cin >> v >> u >> w;
if (v == u) continue;
if (w != 0) {
lc[m] = {w, {v, u}};
++m;
}
g[v].pb(u);
g[u].pb(v);
}
if (s == t) {
cout << 0 << '\n';
return;
}
en[0] = INF;
dfs(s, 0);
for (int i = 0; i < m; i++) {
if (st[lc[i].S.F] > st[lc[i].S.S]) swap(lc[i].S.F, lc[i].S.S);
int v = lc[i].S.F;
id[v] = i; rid[i] = v;
}
id[s] = m; rid[m] = s; id[t] = m + 1; rid[m + 1] = t;
for (int i = 0; i < m; i++) {
int v = lc[i].F;
id[v] = m + 2 + i;
rid[m + 2 + i] = v;
}
for (int i = 0; i <= m + 1 + m; i++) {
for (int j = 0; j <= m + 1 + m; j++) {
for (int x = 0; x < m; x++) {
if (is_in_path(lc[x].S.F, rid[i], rid[j]) && is_in_path(lc[x].S.S, rid[i], rid[j]))
inp[i][j] += (1 << x);
}
}
}
for (int mask = 0; mask < (1 << m); mask++) {
for (int v = 0; v <= m; v++) {
dp[v][mask] = inf;
if ((mask & inp[v][m + 1]) == 0) dp[v][mask] = dis(rid[v], t);
for (int i = 0; i < m; i++) {
if (((1 << i) & mask) == 0) continue;
if (be_anc(lc[i].S.F, rid[v])) {
dp[v][mask] = inf;
break;
}
int w = lc[i].F;
if ((inp[id[w]][v] & mask) == 0 && (inp[id[w]][i] & mask) == 0) {
dp[v][mask] = min(dp[v][mask], dp[i][mask ^ (1 << i)] + dis(rid[v], w) + dis(w, rid[i]));
}
}
}
}
cout << dp[m][(1 << m) - 1];
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q = 1;
// cin >> q;
while (q--) {solve();}
return 0;
}
/*
*/
//shrek is love;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
25044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
25044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
