oj.uz

Submission #1043327

# Submission time Handle Problem Language Result Execution time Memory
1043327 2024-08-04T08:19:26 Z javotaz LOSTIKS (INOI20_lostiks) C++17
36 / 100
 748 ms 120664 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);
		}
	}
	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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 105812 KB Output is correct
2 Correct 40 ms 105808 KB Output is correct
3 Correct 94 ms 112128 KB Output is correct
4 Correct 95 ms 112160 KB Output is correct
5 Correct 99 ms 112208 KB Output is correct
6 Correct 93 ms 112208 KB Output is correct
7 Correct 97 ms 112464 KB Output is correct
8 Correct 105 ms 112212 KB Output is correct
9 Correct 106 ms 112520 KB Output is correct
10 Correct 95 ms 112216 KB Output is correct
11 Correct 98 ms 112428 KB Output is correct
12 Correct 99 ms 114352 KB Output is correct
13 Correct 98 ms 115212 KB Output is correct
14 Correct 101 ms 114108 KB Output is correct
15 Correct 105 ms 114164 KB Output is correct
16 Correct 98 ms 115584 KB Output is correct
17 Correct 97 ms 115540 KB Output is correct
18 Correct 94 ms 116052 KB Output is correct
19 Correct 101 ms 120656 KB Output is correct
20 Correct 102 ms 120656 KB Output is correct
21 Correct 103 ms 120664 KB Output is correct
22 Correct 40 ms 106048 KB Output is correct
23 Correct 41 ms 106072 KB Output is correct
24 Correct 43 ms 105868 KB Output is correct
25 Correct 40 ms 106068 KB Output is correct
26 Incorrect 39 ms 106076 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 105808 KB Output is correct
2 Correct 38 ms 106076 KB Output is correct
3 Correct 38 ms 106068 KB Output is correct
4 Correct 39 ms 105932 KB Output is correct
5 Correct 320 ms 106320 KB Output is correct
6 Correct 333 ms 106320 KB Output is correct
7 Correct 354 ms 106320 KB Output is correct
8 Correct 369 ms 106328 KB Output is correct
9 Correct 366 ms 106540 KB Output is correct
10 Correct 266 ms 106576 KB Output is correct
11 Correct 266 ms 106324 KB Output is correct
12 Correct 276 ms 106540 KB Output is correct
13 Correct 279 ms 106324 KB Output is correct
14 Correct 285 ms 106576 KB Output is correct
15 Correct 410 ms 106832 KB Output is correct
16 Correct 350 ms 106836 KB Output is correct
17 Correct 362 ms 106596 KB Output is correct
18 Correct 288 ms 106556 KB Output is correct
19 Correct 287 ms 106548 KB Output is correct
20 Correct 291 ms 106744 KB Output is correct
21 Correct 281 ms 106808 KB Output is correct
22 Correct 280 ms 107092 KB Output is correct
23 Correct 283 ms 107060 KB Output is correct
24 Correct 275 ms 107144 KB Output is correct
25 Correct 748 ms 106048 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 105812 KB Output is correct
2 Correct 40 ms 105808 KB Output is correct
3 Correct 94 ms 112128 KB Output is correct
4 Correct 95 ms 112160 KB Output is correct
5 Correct 99 ms 112208 KB Output is correct
6 Correct 93 ms 112208 KB Output is correct
7 Correct 97 ms 112464 KB Output is correct
8 Correct 105 ms 112212 KB Output is correct
9 Correct 106 ms 112520 KB Output is correct
10 Correct 95 ms 112216 KB Output is correct
11 Correct 98 ms 112428 KB Output is correct
12 Correct 99 ms 114352 KB Output is correct
13 Correct 98 ms 115212 KB Output is correct
14 Correct 101 ms 114108 KB Output is correct
15 Correct 105 ms 114164 KB Output is correct
16 Correct 98 ms 115584 KB Output is correct
17 Correct 97 ms 115540 KB Output is correct
18 Correct 94 ms 116052 KB Output is correct
19 Correct 101 ms 120656 KB Output is correct
20 Correct 102 ms 120656 KB Output is correct
21 Correct 103 ms 120664 KB Output is correct
22 Correct 40 ms 106048 KB Output is correct
23 Correct 41 ms 106072 KB Output is correct
24 Correct 43 ms 105868 KB Output is correct
25 Correct 40 ms 106068 KB Output is correct
26 Incorrect 39 ms 106076 KB Output isn't correct
27 Halted 0 ms 0 KB -