Submission #633774

#	Time	Username	Problem	Language	Result	Execution time	Memory
633774		NothingXD	LOSTIKS (INOI20_lostiks)	C++14	59 / 100	2094 ms	196348 KiB

Main

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef __uint128_t L;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int maxn = 1e6 + 10;
const int maxm = 20;
const int mask = (1 << 20);
const int inf = 1e9;

int n, m, S, T, edge[maxm][3], comp[maxn], cnt, sz, par[mask][maxm+1], h[maxm+1][maxn], dp[mask][maxm+1];
vector<int> g[maxn];
bool vis[maxn];

int first[maxn], to[maxn << 1], nxt[maxn << 1], ecnt;

void add(int u, int v){
	nxt[++ecnt] = first[u];
	to[ecnt] = v;
	first[u] = ecnt;
}

void dfs(int v, int *h, int p = -1){
	for (int i = first[v]; i; i = nxt[i]){
		int u = to[i];
		if (u != p){
			h[u] = h[v] + 1;
			dfs(u, h, v);
		}
	}
}

void getcomp(int v, int p = -1){
	vis[v] = true;
	comp[v] = cnt;
	for (auto u: g[v]) if (u != p) getcomp(u, v);
}

int getpar(int *par, int v){
	//debug(v, par[v]);
	return (par[v] < 0? v: par[v] = getpar(par, par[v]));
}

void merge(int *par, int u, int v){
	if ((u = getpar(par, u)) == (v = getpar(par, v))) return;
	if (par[u] > par[v]) swap(u, v);
	par[u] += par[v];
	par[v] = u;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n >> S >> T;
	for (int i = 1; i < n; i++){
		int u, v, w; cin >> u >> v >> w;
		add(u, v);
		add(v, u);
		if (w == 0){
			g[u].push_back(v);
			g[v].push_back(u);
		}
		else{
			edge[m][0] = u;
			edge[m][1] = v;
			edge[m][2] = w;
			m++;
		}
	}

	dfs(S, h[m]);

	for (int i = 0; i < m; i++){
		if (h[m][edge[i][0]] > h[m][edge[i][1]]) swap(edge[i][0], edge[i][1]);
		dfs(edge[i][0], h[i]);
	}

	assert(m <= 20);

	for (int i = 1; i <= n; i++){
		if (!vis[i]){
			getcomp(i);
			cnt++;
		}
	}

	for (int i = (1 << m) - 1; ~i; i--){
		if (i == (1 << m) - 1){
			for (int j = 0; j <= m; j++) par[i][j] = -1;
			continue;
		}
		int tmp = __builtin_ctz(((1 << m) - 1) ^ i);
		for (int j = 0; j <= m; j++){
			par[i][j] = par[i^(1 << tmp)][j];
		}
		merge(par[i], comp[edge[tmp][0]], comp[edge[tmp][1]]);
	}

	for (int i = 0; i <= m; i++){
		dp[0][i] = h[i][T];
	}

	for (int msk = 1; msk < (1 << m); msk++){
		for (int i = 0; i <= m; i++){
			int v = (i == m? S: edge[i][0]);
			dp[msk][i] = inf;
			if (getpar(par[msk], comp[T]) == getpar(par[msk], comp[v])){
				dp[msk][i] = h[i][T];
				continue;
			}
			for (int tmp = msk; tmp; tmp ^= tmp & -tmp){
				int j = __builtin_ctz(tmp);
				if (getpar(par[msk], comp[edge[j][2]]) == getpar(par[msk], comp[v]) &&
					   	getpar(par[msk], comp[edge[j][0]]) == getpar(par[msk], comp[v])){
					dp[msk][i] = min(dp[msk][i], dp[msk^(1 << j)][j] + h[i][edge[j][2]] + h[j][edge[j][2]]);
				}
			}
		}
	}

	cout << (dp[(1 << m) - 1][m] == inf? -1: dp[(1 << m) - 1][m]) << '\n';



	return 0;
}

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