oj.uz

Submission #469289

# Submission time Handle Problem Language Result Execution time Memory
469289 2021-08-31T11:03:40 Z sinamhdv LOSTIKS (INOI20_lostiks) C++11
100 / 100
 1244 ms 233448 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 = 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[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(i, 0, m) dp[i].resize(1 << m, INF);
	FOR(i, 0, m) dp[i][0] = 0;

	FOR(mask, 1, 1 << m)
	{
		if (__builtin_popcount(mask) == 1)
		{
			int v = __lg(mask);
			if (!(inp[v] & mask)) dp[v][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[v][mask] = min(dp[v][mask], dp[x][sub] + 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[v][tot]);
	}

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

	cout << ans << endl;

	return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23844 KB Output is correct
2 Correct 13 ms 23824 KB Output is correct
3 Correct 73 ms 37376 KB Output is correct
4 Correct 73 ms 37380 KB Output is correct
5 Correct 72 ms 37396 KB Output is correct
6 Correct 75 ms 37444 KB Output is correct
7 Correct 74 ms 37568 KB Output is correct
8 Correct 72 ms 37544 KB Output is correct
9 Correct 73 ms 37704 KB Output is correct
10 Correct 71 ms 37544 KB Output is correct
11 Correct 72 ms 37496 KB Output is correct
12 Correct 67 ms 39488 KB Output is correct
13 Correct 67 ms 39012 KB Output is correct
14 Correct 69 ms 38588 KB Output is correct
15 Correct 79 ms 39568 KB Output is correct
16 Correct 69 ms 40320 KB Output is correct
17 Correct 70 ms 40328 KB Output is correct
18 Correct 70 ms 40804 KB Output is correct
19 Correct 70 ms 44832 KB Output is correct
20 Correct 71 ms 44740 KB Output is correct
21 Correct 72 ms 44484 KB Output is correct
22 Correct 14 ms 23884 KB Output is correct
23 Correct 15 ms 23884 KB Output is correct
24 Correct 13 ms 23756 KB Output is correct
25 Correct 13 ms 23832 KB Output is correct
26 Correct 14 ms 23756 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23844 KB Output is correct
2 Correct 13 ms 23744 KB Output is correct
3 Correct 13 ms 23840 KB Output is correct
4 Correct 14 ms 23816 KB Output is correct
5 Correct 173 ms 63384 KB Output is correct
6 Correct 149 ms 63492 KB Output is correct
7 Correct 207 ms 63432 KB Output is correct
8 Correct 155 ms 63368 KB Output is correct
9 Correct 174 ms 63388 KB Output is correct
10 Correct 114 ms 63496 KB Output is correct
11 Correct 108 ms 63364 KB Output is correct
12 Correct 108 ms 63420 KB Output is correct
13 Correct 109 ms 63364 KB Output is correct
14 Correct 108 ms 63348 KB Output is correct
15 Correct 155 ms 63496 KB Output is correct
16 Correct 198 ms 63484 KB Output is correct
17 Correct 164 ms 63436 KB Output is correct
18 Correct 110 ms 63508 KB Output is correct
19 Correct 116 ms 63624 KB Output is correct
20 Correct 108 ms 63620 KB Output is correct
21 Correct 108 ms 63604 KB Output is correct
22 Correct 108 ms 63876 KB Output is correct
23 Correct 110 ms 63912 KB Output is correct
24 Correct 109 ms 63864 KB Output is correct
25 Correct 1010 ms 106052 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23844 KB Output is correct
2 Correct 13 ms 23824 KB Output is correct
3 Correct 73 ms 37376 KB Output is correct
4 Correct 73 ms 37380 KB Output is correct
5 Correct 72 ms 37396 KB Output is correct
6 Correct 75 ms 37444 KB Output is correct
7 Correct 74 ms 37568 KB Output is correct
8 Correct 72 ms 37544 KB Output is correct
9 Correct 73 ms 37704 KB Output is correct
10 Correct 71 ms 37544 KB Output is correct
11 Correct 72 ms 37496 KB Output is correct
12 Correct 67 ms 39488 KB Output is correct
13 Correct 67 ms 39012 KB Output is correct
14 Correct 69 ms 38588 KB Output is correct
15 Correct 79 ms 39568 KB Output is correct
16 Correct 69 ms 40320 KB Output is correct
17 Correct 70 ms 40328 KB Output is correct
18 Correct 70 ms 40804 KB Output is correct
19 Correct 70 ms 44832 KB Output is correct
20 Correct 71 ms 44740 KB Output is correct
21 Correct 72 ms 44484 KB Output is correct
22 Correct 14 ms 23884 KB Output is correct
23 Correct 15 ms 23884 KB Output is correct
24 Correct 13 ms 23756 KB Output is correct
25 Correct 13 ms 23832 KB Output is correct
26 Correct 14 ms 23756 KB Output is correct
27 Correct 13 ms 23844 KB Output is correct
28 Correct 13 ms 23744 KB Output is correct
29 Correct 13 ms 23840 KB Output is correct
30 Correct 14 ms 23816 KB Output is correct
31 Correct 173 ms 63384 KB Output is correct
32 Correct 149 ms 63492 KB Output is correct
33 Correct 207 ms 63432 KB Output is correct
34 Correct 155 ms 63368 KB Output is correct
35 Correct 174 ms 63388 KB Output is correct
36 Correct 114 ms 63496 KB Output is correct
37 Correct 108 ms 63364 KB Output is correct
38 Correct 108 ms 63420 KB Output is correct
39 Correct 109 ms 63364 KB Output is correct
40 Correct 108 ms 63348 KB Output is correct
41 Correct 155 ms 63496 KB Output is correct
42 Correct 198 ms 63484 KB Output is correct
43 Correct 164 ms 63436 KB Output is correct
44 Correct 110 ms 63508 KB Output is correct
45 Correct 116 ms 63624 KB Output is correct
46 Correct 108 ms 63620 KB Output is correct
47 Correct 108 ms 63604 KB Output is correct
48 Correct 108 ms 63876 KB Output is correct
49 Correct 110 ms 63912 KB Output is correct
50 Correct 109 ms 63864 KB Output is correct
51 Correct 1010 ms 106052 KB Output is correct
52 Correct 1179 ms 163824 KB Output is correct
53 Correct 1180 ms 163692 KB Output is correct
54 Correct 1162 ms 161220 KB Output is correct
55 Correct 1193 ms 160964 KB Output is correct
56 Correct 1181 ms 162008 KB Output is correct
57 Correct 1182 ms 163680 KB Output is correct
58 Correct 13 ms 23756 KB Output is correct
59 Correct 14 ms 23756 KB Output is correct
60 Correct 14 ms 23872 KB Output is correct
61 Correct 1188 ms 163836 KB Output is correct
62 Correct 1244 ms 160760 KB Output is correct
63 Correct 1189 ms 161032 KB Output is correct
64 Correct 116 ms 39380 KB Output is correct
65 Correct 85 ms 39816 KB Output is correct
66 Correct 1161 ms 164092 KB Output is correct
67 Correct 1203 ms 163668 KB Output is correct
68 Correct 1078 ms 159084 KB Output is correct
69 Correct 1066 ms 159580 KB Output is correct
70 Correct 1074 ms 158992 KB Output is correct
71 Correct 1137 ms 158916 KB Output is correct
72 Correct 1153 ms 158892 KB Output is correct
73 Correct 1008 ms 160324 KB Output is correct
74 Correct 1028 ms 161220 KB Output is correct
75 Correct 1046 ms 160956 KB Output is correct
76 Correct 1010 ms 161852 KB Output is correct
77 Correct 1004 ms 160704 KB Output is correct
78 Correct 1012 ms 168508 KB Output is correct
79 Correct 1018 ms 168028 KB Output is correct
80 Correct 970 ms 166596 KB Output is correct
81 Correct 901 ms 182980 KB Output is correct
82 Correct 938 ms 184644 KB Output is correct
83 Correct 943 ms 184556 KB Output is correct
84 Correct 939 ms 195524 KB Output is correct
85 Correct 962 ms 233448 KB Output is correct
86 Correct 976 ms 232628 KB Output is correct
87 Correct 979 ms 232740 KB Output is correct