Submission #789558

#	Time	Username	Problem	Language	Result	Execution time	Memory
789558		MISM06	LOSTIKS (INOI20_lostiks)	C++14	100 / 100	1717 ms	395568 KiB

Main

//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], dis[M * 2][M * 2];
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;
}
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);
				int xx = rid[i], y = rid[j];
				dis[i][j] = h[xx] + h[y] - 2 * h[lca(xx, y)];
			}
		}
	}
	for (int mask = 0; mask < (1 << m); mask++) {
		for (int v = 0; v <= m; v++) {
			dp[v][mask] = inf;
			if (inp[v][m] & mask) continue;
			if ((mask & inp[v][m + 1]) == 0) dp[v][mask] = dis[v][id[t]];
			for (int i = 0; i < m; i++) {
				if (((1 << i) & mask) == 0) continue;
				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[v][id[w]] + dis[id[w]][i]);
				}
			}
		}
	}
	if (dp[m][(1 << m) - 1] >= inf) cout << -1 << '\n';
	else 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;

• Subtask 1: 23 / 23
• Subtask 2: 36 / 36
• Subtask 3: 41 / 41