oj.uz

답안 #469273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469273 2021-08-31T10:32:26 Z sinamhdv LOSTIKS (INOI20_lostiks) C++11
0 / 100
 81 ms 41156 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);

	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] + MAXE, 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;

	int tot = inp[laste] | (1 << laste);
	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]);
	}

	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 16 ms 24004 KB Output is correct
2 Correct 13 ms 24012 KB Output is correct
3 Correct 77 ms 39104 KB Output is correct
4 Correct 72 ms 39184 KB Output is correct
5 Correct 71 ms 39316 KB Output is correct
6 Correct 74 ms 39120 KB Output is correct
7 Correct 75 ms 39228 KB Output is correct
8 Correct 81 ms 39196 KB Output is correct
9 Correct 79 ms 39424 KB Output is correct
10 Correct 73 ms 39196 KB Output is correct
11 Correct 76 ms 39272 KB Output is correct
12 Incorrect 68 ms 41156 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

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

Subtask #3
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 24004 KB Output is correct
2 Correct 13 ms 24012 KB Output is correct
3 Correct 77 ms 39104 KB Output is correct
4 Correct 72 ms 39184 KB Output is correct
5 Correct 71 ms 39316 KB Output is correct
6 Correct 74 ms 39120 KB Output is correct
7 Correct 75 ms 39228 KB Output is correct
8 Correct 81 ms 39196 KB Output is correct
9 Correct 79 ms 39424 KB Output is correct
10 Correct 73 ms 39196 KB Output is correct
11 Correct 76 ms 39272 KB Output is correct
12 Incorrect 68 ms 41156 KB Output isn't correct
13 Halted 0 ms 0 KB -