Submission #1279441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279441		enxiayy	LOSTIKS (INOI20_lostiks)	C++20	100 / 100	1131 ms	235204 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;

template<class T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; }
template<class T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }

const int N = 1e6 + 5;
const int LOG = 20;

struct locked_route {
	int u, v, h, id;

	locked_route(int u = 0, int v = 0, int h = 0, int id = 0) : u(u), v(v), h(h), id(id) {}
};

int n, m, s, t;
vector<pii> adj[N];
vector<locked_route> lkr;

namespace HLD {
	int tin[N], tout[N], id[N], siz[N], high[N], dist[N], par[N], head[N], timer_dfs = 0, cur_chain = 0;

	void dfs(int u) {
		siz[u] = 1;
		tin[u] = ++timer_dfs;
		for(auto [v, w] : adj[u]) {if (v == par[u]) continue;
			high[v] = high[u] + 1;
			dist[v] = dist[u] ^ w;
			par[v] = u;
			dfs(v);
			siz[u] += siz[v];
		}
		tout[u] = timer_dfs;
	}

	void dfs2(int u) {
		if (head[cur_chain] == 0) {
			head[cur_chain] = u;
		}
		id[u] = cur_chain;
		int fat = 0;
		for(auto [v, w] : adj[u]) { if (v == par[u]) continue;
			if (siz[fat] < siz[v]) {
				fat = v;
			}
		}
		if (fat != 0) dfs2(fat);

		for(auto [v, w] : adj[u]) {
			if (v == par[u] || v == fat) continue;
			++cur_chain;
			dfs2(v);
		}
	}

	int get_lca(int u, int v) {
		while(id[u] != id[v]) {
			if (id[u] < id[v]) swap(u, v);
			u = par[head[id[u]]];
		}
		return (high[u] < high[v] ? u : v);
	}

	void preapre_lca() {
		dfs(1);
		dfs2(1);
	}

	int get_dist(int u, int v) {
		return high[u] + high[v] - 2 * high[get_lca(u, v)];
	}

	int get_locked(int u, int v) {
		return dist[u] ^ dist[v];
	}
} using namespace HLD;

bool is_sub(int v, int acs) {
	return tin[acs] <= tin[v] && tout[v] <= tout[acs];
}

int key[N], target[N];
ll dp[20][(1 << 20)];

bool can_go(int u, int v, int mask) {
	int sub = get_locked(u, v);
	return ((sub & mask) == sub);
}

void solve() {
	cin >> n >> s >> t;
	FOR(i, 1, n - 1) {
		int u, v, h;
		cin >> u >> v >> h;
		int w = 0;
		if (h != 0) {
			w = (1 << sz(lkr));
			lkr.eb(u, v, h, sz(lkr));
			++m;
		}
		adj[u].eb(v, w);
		adj[v].eb(u, w);

 	}

	preapre_lca();

	if (can_go(s, t, 0)) {
		cout << get_dist(s, t) << el;
		return;
	}


	for(auto _ : lkr) {
		int u = _.u;
		int v = _.v;
		int h = _.h;
		int id = _.id;

		key[id] = h;
		if (high[u] > high[v]) swap(u, v);
		target[id] = (is_sub(s, v) ? v : u);
	}

	FOR(i, 0, m - 1) {
		REP(mask, 0, (1 << m))
			dp[i][mask] = LLONG_MAX;
	}


	FOR(i, 0, m - 1) {
		if (can_go(s, key[i], 0) && can_go(key[i], target[i], 0)) {
			dp[i][(1 << i)] = get_dist(s, key[i]) + get_dist(key[i], target[i]);
		}
	}

	ll ans = LLONG_MAX;
	REP(mask, 0, (1 << m)) {
		FOR(i, 0, m - 1) {
			if (dp[i][mask] == LLONG_MAX) continue;

			FOR(j, 0, m - 1) {
				if (!(mask >> j & 1)) {
					if (can_go(target[i], key[j], mask) &&
						can_go(key[j], target[j], mask)) {
							minimize(dp[j][mask | (1 << j)],
							dp[i][mask] + get_dist(target[i], key[j])
										+ get_dist(key[j], target[j]));
						}
				}
			}

			if (can_go(target[i], t, mask)) {
				minimize(ans, dp[i][mask] + get_dist(target[i], t));
			}
		}
	}

	cout << (ans == LLONG_MAX ? -1 : ans) << el;
}

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

	#define task "test"
	if(fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	solve();

	return 0;
}

/*

*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:192:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:193:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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