oj.uz

답안 #469262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469262 2021-08-31T10:04:13 Z sinamhdv LOSTIKS (INOI20_lostiks) C++11
0 / 100
 94 ms 42504 KB 
#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 = 1000100;
const int MAXE = 22;
const int LOGN = 25;

int n, s, t, m;
int ef[MAXN], eto[MAXN], ky[MAXN], kind[MAXN];
vector<int> adj[MAXN];
int lpar[LOGN][MAXN];
int h[MAXN];
int pth[MAXN];
int lck[MAXE];
int dp[1 << 20][MAXE];
int inp[MAXE];
int cost[MAXE][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);
	}
}

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);
	dbgr(kind, kind + 3);

	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;
	}

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

	FOR(mask, 1, 1 << m) fill(dp[mask], dp[mask] + m, INF);

	FOR(mask, 1, 1 << m)
	{
		if (__builtin_popcount(mask) == 1)
		{
			dp[mask][__lg(mask)] = 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;
	dbg(laste);

	int tot = inp[laste] | (1 << laste);
	dbg(tot);
	int ans = INF;
	FOR(v, 0, m)
	{
		int cs = h[ky[lck[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]);
	}

	dbg(ans);

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

	cout << ans << endl;

	return 0;
}

Subtask #1
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23956 KB Output is correct
2 Correct 16 ms 24008 KB Output is correct
3 Correct 94 ms 40516 KB Output is correct
4 Correct 80 ms 40456 KB Output is correct
5 Correct 86 ms 40544 KB Output is correct
6 Correct 72 ms 40448 KB Output is correct
7 Correct 86 ms 40588 KB Output is correct
8 Correct 88 ms 40548 KB Output is correct
9 Correct 78 ms 40736 KB Output is correct
10 Correct 77 ms 40680 KB Output is correct
11 Correct 75 ms 40588 KB Output is correct
12 Incorrect 69 ms 42504 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24012 KB Output is correct
2 Correct 14 ms 24008 KB Output is correct
3 Correct 13 ms 24044 KB Output is correct
4 Incorrect 14 ms 24068 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23956 KB Output is correct
2 Correct 16 ms 24008 KB Output is correct
3 Correct 94 ms 40516 KB Output is correct
4 Correct 80 ms 40456 KB Output is correct
5 Correct 86 ms 40544 KB Output is correct
6 Correct 72 ms 40448 KB Output is correct
7 Correct 86 ms 40588 KB Output is correct
8 Correct 88 ms 40548 KB Output is correct
9 Correct 78 ms 40736 KB Output is correct
10 Correct 77 ms 40680 KB Output is correct
11 Correct 75 ms 40588 KB Output is correct
12 Incorrect 69 ms 42504 KB Output isn't correct
13 Halted 0 ms 0 KB -