oj.uz

Submission #1043344

# Submission time Handle Problem Language Result Execution time Memory
1043344 2024-08-04T08:37:50 Z javotaz LOSTIKS (INOI20_lostiks) C++17
59 / 100
 2000 ms 120716 KB 
// In the Name of Allah

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

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,avx,avx2,sse4.2,popcnt,tune=native")

typedef long long ll;

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

const int N = 1e6 + 12, M = 20, inf = 2e9 + 7;
vector<pii> g[N];
int n, s, t, par[N], dp[(1 << M) + 4][M], p[N], kd[N], bt[M], sz, pd[N], e[N];
pii f[2 * M + 2][2 * M + 2];
bool mrk[N];
vector<int> v, d;

void ip() {
	cin >> n >> s >> t;
	for (int i = 1; i < n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
}

void dfs(int u) {
	for (auto i: g[u])
		if (i.F != par[u]) { 
			par[i.F] = u;
			e[i.F] = e[u] + 1;
			if (i.S) {
				pd[i.F] = d.size(), d.pb(i.F), kd[i.F] = i.S;
				v.pb(u), v.pb(i.S);
			}
			dfs(i.F);
		}
}

void dfs2(int u, int rt, int h = 0, int mask = 0, int par = -1) {
	if (mrk[u])
		f[rt][p[u]] = {h, mask};
	for (auto i: g[u])
		if (i.F != par)
			dfs2(i.F, rt, h + 1, (i.S? (mask | (1 << pd[(e[u] < e[i.F])? i.F : u])) : mask), u);
}

void solve() {
	par[s] = s;
	dfs(s);
	v.pb(s), v.pb(t);
	sort(all(v));
	v.resize(unique(all(v)) - v.begin());
	for (int i = 0; i < v.size(); i++) 
		p[v[i]] = i, mrk[v[i]] = true;
	for (int i = 0; i < v.size(); i++)
		dfs2(v[i], i);
	memset(dp, 127, sizeof dp);
	int c = d.size();
	int ans = inf;
	for (int mask = 1; mask < (1 << c); ++mask) {
		sz = 0;
		for (int i = 0; i < c; i++)
			if ((mask >> i) & 1)
				bt[sz++] = i;
		for (int id1 = 0; id1 < sz; ++id1) {
			int i = bt[id1];
			int u = d[i], ku = kd[d[i]], x = mask ^ (1 << i);
			if (__builtin_popcount(mask) == 1) {
				if (f[p[s]][p[ku]].S == x && f[p[ku]][p[par[u]]].S == x)
					dp[mask][i] = f[p[s]][p[ku]].F + f[p[ku]][p[par[u]]].F;
			}
			else {
				for (int id2 = 0; id2 < c; ++id2)
					if (id2 != id1) {
						int j = bt[id2], v = d[bt[id2]];
						if ((f[p[par[v]]][p[ku]].S | x) == x && (f[p[ku]][p[par[u]]].S | x) == x)
							dp[mask][i] = min(dp[mask][i], dp[x][j] + f[p[par[v]]][p[ku]].F + f[p[ku]][p[par[u]]].F);
					}
			}
			if ((f[p[par[u]]][p[t]].S | mask) == mask)
				ans = min(ans, dp[mask][i] + f[p[par[u]]][p[t]].F);
		}
	}
	if (f[p[s]][p[t]].S == 0)
		ans = f[p[s]][p[t]].F;
	cout << ((ans == inf)? -1 : ans) << '\n';
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ip(), solve();
	return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
Main.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 105808 KB Output is correct
2 Correct 41 ms 105936 KB Output is correct
3 Correct 92 ms 112116 KB Output is correct
4 Correct 89 ms 112212 KB Output is correct
5 Correct 99 ms 112268 KB Output is correct
6 Correct 104 ms 112208 KB Output is correct
7 Correct 98 ms 112464 KB Output is correct
8 Correct 96 ms 112212 KB Output is correct
9 Correct 99 ms 112464 KB Output is correct
10 Correct 91 ms 112224 KB Output is correct
11 Correct 97 ms 112208 KB Output is correct
12 Correct 96 ms 114516 KB Output is correct
13 Correct 94 ms 115188 KB Output is correct
14 Correct 99 ms 114000 KB Output is correct
15 Correct 98 ms 114256 KB Output is correct
16 Correct 109 ms 115364 KB Output is correct
17 Correct 101 ms 115540 KB Output is correct
18 Correct 104 ms 116192 KB Output is correct
19 Correct 108 ms 120656 KB Output is correct
20 Correct 117 ms 120660 KB Output is correct
21 Correct 106 ms 120716 KB Output is correct
22 Correct 43 ms 106064 KB Output is correct
23 Correct 40 ms 106044 KB Output is correct
24 Correct 40 ms 106068 KB Output is correct
25 Correct 40 ms 105916 KB Output is correct
26 Correct 43 ms 106064 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 105808 KB Output is correct
2 Correct 40 ms 105812 KB Output is correct
3 Correct 44 ms 105904 KB Output is correct
4 Correct 37 ms 106068 KB Output is correct
5 Correct 345 ms 106320 KB Output is correct
6 Correct 375 ms 106304 KB Output is correct
7 Correct 387 ms 106324 KB Output is correct
8 Correct 411 ms 106320 KB Output is correct
9 Correct 403 ms 106416 KB Output is correct
10 Correct 285 ms 106568 KB Output is correct
11 Correct 334 ms 106352 KB Output is correct
12 Correct 281 ms 106320 KB Output is correct
13 Correct 295 ms 106320 KB Output is correct
14 Correct 276 ms 106496 KB Output is correct
15 Correct 373 ms 106580 KB Output is correct
16 Correct 352 ms 106576 KB Output is correct
17 Correct 345 ms 106580 KB Output is correct
18 Correct 283 ms 106580 KB Output is correct
19 Correct 282 ms 106576 KB Output is correct
20 Correct 312 ms 106576 KB Output is correct
21 Correct 291 ms 106996 KB Output is correct
22 Correct 281 ms 107092 KB Output is correct
23 Correct 282 ms 107056 KB Output is correct
24 Correct 274 ms 107088 KB Output is correct
25 Correct 760 ms 106048 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 105808 KB Output is correct
2 Correct 41 ms 105936 KB Output is correct
3 Correct 92 ms 112116 KB Output is correct
4 Correct 89 ms 112212 KB Output is correct
5 Correct 99 ms 112268 KB Output is correct
6 Correct 104 ms 112208 KB Output is correct
7 Correct 98 ms 112464 KB Output is correct
8 Correct 96 ms 112212 KB Output is correct
9 Correct 99 ms 112464 KB Output is correct
10 Correct 91 ms 112224 KB Output is correct
11 Correct 97 ms 112208 KB Output is correct
12 Correct 96 ms 114516 KB Output is correct
13 Correct 94 ms 115188 KB Output is correct
14 Correct 99 ms 114000 KB Output is correct
15 Correct 98 ms 114256 KB Output is correct
16 Correct 109 ms 115364 KB Output is correct
17 Correct 101 ms 115540 KB Output is correct
18 Correct 104 ms 116192 KB Output is correct
19 Correct 108 ms 120656 KB Output is correct
20 Correct 117 ms 120660 KB Output is correct
21 Correct 106 ms 120716 KB Output is correct
22 Correct 43 ms 106064 KB Output is correct
23 Correct 40 ms 106044 KB Output is correct
24 Correct 40 ms 106068 KB Output is correct
25 Correct 40 ms 105916 KB Output is correct
26 Correct 43 ms 106064 KB Output is correct
27 Correct 39 ms 105808 KB Output is correct
28 Correct 40 ms 105812 KB Output is correct
29 Correct 44 ms 105904 KB Output is correct
30 Correct 37 ms 106068 KB Output is correct
31 Correct 345 ms 106320 KB Output is correct
32 Correct 375 ms 106304 KB Output is correct
33 Correct 387 ms 106324 KB Output is correct
34 Correct 411 ms 106320 KB Output is correct
35 Correct 403 ms 106416 KB Output is correct
36 Correct 285 ms 106568 KB Output is correct
37 Correct 334 ms 106352 KB Output is correct
38 Correct 281 ms 106320 KB Output is correct
39 Correct 295 ms 106320 KB Output is correct
40 Correct 276 ms 106496 KB Output is correct
41 Correct 373 ms 106580 KB Output is correct
42 Correct 352 ms 106576 KB Output is correct
43 Correct 345 ms 106580 KB Output is correct
44 Correct 283 ms 106580 KB Output is correct
45 Correct 282 ms 106576 KB Output is correct
46 Correct 312 ms 106576 KB Output is correct
47 Correct 291 ms 106996 KB Output is correct
48 Correct 281 ms 107092 KB Output is correct
49 Correct 282 ms 107056 KB Output is correct
50 Correct 274 ms 107088 KB Output is correct
51 Correct 760 ms 106048 KB Output is correct
52 Execution timed out 2041 ms 91772 KB Time limit exceeded
53 Halted 0 ms 0 KB -