Submission #469287

#	Time	Username	Problem	Language	Result	Execution time	Memory
469287		sinamhdv	LOSTIKS (INOI20_lostiks)	C++11	100 / 100	1276 ms	258364 KiB

Main

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define fast_io ios::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

const int MAXN = 1000010;
const int MAXE = 22;
const int LOGN = 21;

int n, s, t, m;
int ef[MAXN], eto[MAXN], ky[MAXN], kind[MAXN];
vector<int> adj[MAXN];
vector<int> lpar[LOGN];
int h[MAXN];
int pth[MAXN];
int lck[MAXE];
vector<int> dp[1 << 20];
int inp[MAXE];
int cost[MAXE][MAXE];
int tot;
int ldis[MAXE];

void dfs(int v)
{
	for (int e : adj[v])
	{
		int u = ef[e] ^ eto[e] ^ v;
		if (u == lpar[0][v]) continue;
		lpar[0][u] = v;
		h[u] = h[v] + 1;
		pth[u] = pth[v] | (ky[e] ? (1 << kind[e]) : 0);
		dfs(u);
	}
}

void bkdfs(int v)
{
	tot |= (1 << v);
	FOR(i, 0, m) if ((inp[v] >> i & 1) && !(tot >> i & 1)) bkdfs(i);
}

inline int getpar(int x, int d)
{
	FOR(i, 0, LOGN) if (d >> i & 1) x = lpar[i][x];
	return x;
}

inline int getlca(int x, int y)
{
	if (h[x] > h[y]) swap(x, y);
	y = getpar(y, h[y] - h[x]);
	if (x == y) return x;
	for (int i = LOGN - 1; i >= 0; i--)
	{
		if (lpar[i][x] != lpar[i][y])
		{
			x = lpar[i][x];
			y = lpar[i][y];
		}
	}
	return lpar[0][x];
}

int32_t main(void)
{
	fast_io;
	cin >> n >> s >> t;
	FOR(i, 0, n - 1)
	{
		cin >> ef[i] >> eto[i] >> ky[i];
		adj[ef[i]].pb(i);
		adj[eto[i]].pb(i);
		if (ky[i])
		{
			lck[m] = i;
			kind[i] = m;
			m++;
		}
	}

	dbg(m);

	FOR(i, 0, LOGN) lpar[i].resize(n + 5);
	dfs(s);

	dbgr(pth + 1, pth + n + 1);
	if (pth[t] == 0)
	{
		return cout << h[t] << endl, 0;
	}

	FOR(i, 0, n - 1) if (h[ef[i]] > h[eto[i]]) swap(ef[i], eto[i]);

	FOR(i, 1, LOGN) FOR(j, 1, n + 1) lpar[i][j] = lpar[i - 1][lpar[i - 1][j]];

	FOR(i, 0, m)
	{
		int e = lck[i];
		inp[i] = (pth[ef[e]] | pth[ky[e]]);
	}

	FOR(i, 0, m) FOR(j, 0, m) if (i != j)
	{
		int x = ef[lck[i]];
		int y = ky[lck[j]];
		int z = ef[lck[j]];
		cost[i][j] = h[x] + h[y] - 2 * h[getlca(x, y)] + h[y] + h[z] - 2 * h[getlca(y, z)];

//		cout << i << ' ' << j << ' ' << cost[i][j] << endl;
	}


	FOR(i, 0, m)
	{
		ldis[i] = h[ef[lck[i]]] + h[ky[lck[i]]] - 2 * h[getlca(ef[lck[i]], ky[lck[i]])];
	}

	FOR(i, 0, LOGN)
	{
		lpar[i].clear();
		lpar[i].shrink_to_fit();
	}

	dbgr(h + 1, h + n + 1);
	dbgr(pth + 1, pth + n + 1);
	dbgr(lck, lck + m);
	dbgr(inp, inp + m);

	FOR(mask, 0, 1 << m) dp[mask].resize(m, INF);
	fill(all(dp[0]), 0);
//	FOR(mask, 1, 1 << m) fill(dp[mask], dp[mask] + m, INF);

	FOR(mask, 1, 1 << m)
	{
		if (__builtin_popcount(mask) == 1)
		{
			int v = __lg(mask);
			if (!(inp[v] & mask)) dp[mask][v] = 0;
			continue;
		}
		FOR(v, 0, m)
		{
			if ((mask >> v & 1) && (inp[v] & mask) == 0)
			{
				int sub = mask ^ (1 << v);
				FOR(x, 0, m) if (sub >> x & 1)
				{
					dp[mask][v] = min(dp[mask][v], dp[sub][x] + cost[v][x]);
				}
			}
		}
	}

//	FOR(mask, 0, 1 << m) FOR(v, 0, m) cout << v << ' ' << mask << ' ' << dp[mask][v] << endl;

	int laste = -1;
	FOR(i, 0, m) if (pth[t] >> i & 1) if (laste == -1 || h[ef[lck[i]]] > h[ef[lck[laste]]]) laste = i;

	bkdfs(laste);
	int ans = INF;
	FOR(v, 0, m)
	{
		int cs = h[ky[lck[v]]] + ldis[v]; //h[ky[lck[v]]] + h[ef[lck[v]]] - 2 * h[getlca(ky[lck[v]], ef[lck[v]])];
		ans = min(ans, cs + dp[tot][v]);
	}

	if (ans >= INF) return cout << "-1\n", 0;
	ans += h[t] - h[ef[lck[laste]]];

	cout << ans << endl;

	return 0;
}

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