Submission #624113

#	Time	Username	Problem	Language	Result	Execution time	Memory
624113		Arinoor	LOSTIKS (INOI20_lostiks)	C++17	100 / 100	1764 ms	425740 KiB

Main

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

#define pb				push_back
#define mp				make_pair
#define fi				first
#define se				second
#define all(x)			x.begin(), x.end()
#define bug(x)			cout << #x << " : " << x << '\n'
#define ios				ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e6 + 10;
const int maxm = 30;
const int maxlg = 20;
const int mod = 1e9 + 7;
const ll inf = 1e17 + 10;

int e[maxn], h[maxn], par[maxn][maxlg], lck[maxn][maxlg], V[maxm], ind[maxn];
int dt[maxm], dl[maxm];
int d[maxm][maxm], l[maxm][maxm];
ll dp[1 << maxlg][maxm];
vector<pii> E;
vector<pii> edge;
vector<int> G[maxn], S;

void dfs(int v, int p = 0, int pe = -1){
	par[v][0] = p;
	if(~pe)
		lck[v][0] = 1 << pe;
	for(int i = 1; i < maxlg and par[v][i - 1]; i ++){
		par[v][i] = par[par[v][i - 1]][i - 1];
		lck[v][i] = lck[v][i - 1] | lck[par[v][i - 1]][i - 1];
	}
	for(int eg : G[v]){
		int u = edge[eg].fi + edge[eg].se - v;
		if(u != p){
			h[u] = h[v] + 1;
			dfs(u, v, e[eg]);
		}
	}
}

int get_par(int v, int h){
	for(int i = 0; i < maxlg; i ++)
		if(h >> i & 1)
			v = par[v][i];
	return v;
}

int get_lock(int v, int h){
	int res = 0;
	for(int i = 0; i < maxlg; i ++){
		if(h >> i & 1){
			res |= lck[v][i];
			v = par[v][i];
		}
	}
	return res;
}

int lca(int v, int u){
	if(h[v] < h[u])
		swap(u, v);
	v = get_par(v, h[v] - h[u]);
	if(v == u)
		return v;
	for(int i = maxlg - 1; ~i; i --){
		if(par[v][i] ^ par[u][i]){
			v = par[v][i];
			u = par[u][i];
		}
	}
	return par[v][0];
}

int dist(int u, int v){
	int w = lca(u, v);
	return h[v] + h[u] - 2 * h[w];
}

int lock_path(int u, int v){
	int w = lca(u, v);
	return get_lock(u, h[u] - h[w]) | get_lock(v, h[v] - h[w]);
}

int main(){
	ios;
	int n, s, t;
	cin >> n >> s >> t;
	for(int i = 0; i < n - 1; i ++){
		int u, v, w;
		cin >> u >> v >> w;
		edge.pb(mp(u, v));
		G[u].pb(i);
		G[v].pb(i);
		if(w){
			e[i] = E.size();
			E.pb(mp(i, w));
		}
		else{
			e[i] = -1;
		}
	}
	dfs(1);
	int m = E.size();
	for(int i = 0; i < m; i ++){
		int u = edge[E[i].fi].fi;
		int v = edge[E[i].fi].se;
		if(dist(E[i].se, u) < dist(E[i].se, v))
			V[i] = u;
		else
			V[i] = v;
		S.pb(V[i]);
	}
	S.pb(s);
	sort(all(S));
	S.resize(unique(all(S)) - S.begin());
	for(int v : S)
		ind[v] = lower_bound(all(S), v) - S.begin();
	n = S.size();
	for(int i = 0; i < n; i ++){
		int v = S[i];
		dt[i] = dist(v, t);
		dl[i] = lock_path(v, t);
		for(int j = 0; j < m; j ++){
			int u = V[j];
			int w = E[j].se;
			d[i][j] = dist(v, w) + dist(w, u);
			l[i][j] = lock_path(v, w) | lock_path(w, u);
		}
	}
	for(int msk = 0; msk < 1 << m; msk ++){
		for(int i = 0; i < n; i ++){
			if(!(dl[i] & msk)){
				dp[msk][i] = dt[i];
				continue;
			}
			dp[msk][i] = inf;
			for(int msk2 = msk; ; msk2 -= msk2 & -msk2){
				if(!msk2) break;
				int bit = __builtin_ctz(msk2);
				if(!(l[i][bit] & msk)){
					dp[msk][i] = min(dp[msk][i], d[i][bit] + dp[msk ^ (1 << bit)][ind[V[bit]]]);
				}
			}
		}
	}
	if(dp[(1 << m) - 1][ind[s]] >= inf)
		cout << "-1\n";
	else
		cout << dp[(1 << m) - 1][ind[s]] << '\n';
}

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