oj.uz

Submission #773731

# Submission time Handle Problem Language Result Execution time Memory
773731 2023-07-05T08:01:53 Z ParsaS LOSTIKS (INOI20_lostiks) C++17
59 / 100
 2000 ms 322548 KB 
// In the name of God
//#pragma GCC optimize("O2", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e6 + 5, lg = 20;
int n, c, s, t;
vector<int> adj[N];
vector<pair<int, int> > E;
int f[N], tin[N], tout[N], T, h[N], up[N][lg];
int dis[lg][lg + 2], F[N];
ll dp[1 << lg][lg];
bool ok[1 << lg][lg + 2];

void dfs(int v, int p) {
    tin[v] = ++T;
    up[v][0] = p;
    for (int i = 1; i < lg; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (auto u : adj[v]) {
        if (u != p) {
            h[u] = h[v] + 1;
            dfs(u, v);
        }
    }
    tout[v] = ++T;
}
void dfs2(int v, int p, int k) {
    for (auto u : adj[v]) {
        if (u != p) {
            dis[k][u] = dis[k][v] + 1;
            dfs2(u, v, k);
        }
    }
}
bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int lca(int v, int u) {
    if (tin[v] > tin[u])
        swap(v, u);
    if (anc(v, u))
        return v;
    for (int i = lg - 1; i >= 0; i--)
        if (!anc(up[u][i], v))
            u = up[u][i];
    return up[u][0];
}
void solve() {
	set<int> st;
    cin >> n >> s >> t;
    for (int i = 0; i < n - 1; i++) {
        int v, u, w; cin >> v >> u >> w;
        adj[v].pb(u), adj[u].pb(v);
        if (w) {
            f[(int)E.size()] = w, E.pb(mp(v, u));
            st.insert(w);
        }
    }
	st.insert(t);
    dfs(s, 0);
    tout[0] = ++T;
    int tmp = 0;
    for (auto x : st) {
        F[x] = tmp++;
    }
    c = (int)E.size();
    assert(c <= 20);
    memset(dis, 63, sizeof dis);

    for (int i = 0; i < c; i++) {
        if (tin[E[i].fi] > tin[E[i].se])
            swap(E[i].fi, E[i].se);
        //dfs2(E[i].fi, 0, i);
        for (auto v : st) {
            //assert(dis[i][v] == h[E[i].fi] + h[v] - 2 * h[lca(E[i].fi, v)]);
            dis[i][F[v]] = h[E[i].fi] + h[v] - 2 * h[lca(E[i].fi, v)];
        }
    }
    E.pb(mp(t, t));
    f[c] = t;
    for (int mask = 0; mask < (1 << c); mask++) {
        for (int i = 0; i <= c; i++) {
            int v = E[i].fi;
            ok[mask][i] = true;
            for (int j = 0; j < c; j++) {
                ok[mask][i] &= (mask & (1 << j)) || (!anc(E[j].se, v) && !anc(E[j].se, f[i]));
            }
        }
    }
    memset(dp, 63, sizeof dp);
    for (int i = 0; i < c; i++) {
        if (ok[1 << i][i]) {
            dp[1 << i][i] = h[f[i]] + dis[i][F[f[i]]];
        }
    }
    ll ans = 1e18;
    if (ok[0][c]) {
        ans = h[t];
    }
    for (int mask = 1; mask < (1 << c); mask++) {
        for (int i = 0; i < c; i++) {
            if (!(mask & (1 << i)))
                continue;

            int mask2 = mask ^ (1 << i);
            for (int j = 0; j < c; j++) {
                if (mask2 & (1 << j)) {
                    if (ok[mask2][i]) {
                        dp[mask][i] = min(dp[mask][i], dp[mask2][j] + dis[j][F[f[i]]] + dis[i][F[f[i]]]);
                    }
                }
            }

            if (ok[mask][c]) {
                ans = min(ans, dp[mask][i] + dis[i][F[t]]);
            }
        }
    }

    if (ans < 1e18)
        cout << ans << '\n';
    else
        cout << -1 << '\n';
}

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

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 187916 KB Output is correct
2 Correct 62 ms 187920 KB Output is correct
3 Correct 111 ms 200396 KB Output is correct
4 Correct 123 ms 200348 KB Output is correct
5 Correct 108 ms 200408 KB Output is correct
6 Correct 111 ms 200312 KB Output is correct
7 Correct 109 ms 200468 KB Output is correct
8 Correct 114 ms 200404 KB Output is correct
9 Correct 113 ms 200580 KB Output is correct
10 Correct 110 ms 200428 KB Output is correct
11 Correct 123 ms 200392 KB Output is correct
12 Correct 110 ms 201948 KB Output is correct
13 Correct 110 ms 201568 KB Output is correct
14 Correct 118 ms 201236 KB Output is correct
15 Correct 125 ms 202072 KB Output is correct
16 Correct 112 ms 202596 KB Output is correct
17 Correct 110 ms 202692 KB Output is correct
18 Correct 115 ms 203100 KB Output is correct
19 Correct 114 ms 206316 KB Output is correct
20 Correct 119 ms 206132 KB Output is correct
21 Correct 115 ms 205916 KB Output is correct
22 Correct 64 ms 187912 KB Output is correct
23 Correct 62 ms 187976 KB Output is correct
24 Correct 62 ms 187928 KB Output is correct
25 Correct 62 ms 187956 KB Output is correct
26 Correct 63 ms 188024 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 187980 KB Output is correct
2 Correct 63 ms 187980 KB Output is correct
3 Correct 61 ms 187992 KB Output is correct
4 Correct 60 ms 188052 KB Output is correct
5 Correct 1299 ms 200184 KB Output is correct
6 Correct 1328 ms 200128 KB Output is correct
7 Correct 1296 ms 200192 KB Output is correct
8 Correct 1304 ms 200236 KB Output is correct
9 Correct 1308 ms 200064 KB Output is correct
10 Correct 1125 ms 200196 KB Output is correct
11 Correct 1118 ms 200208 KB Output is correct
12 Correct 1115 ms 200280 KB Output is correct
13 Correct 1112 ms 200152 KB Output is correct
14 Correct 1098 ms 200268 KB Output is correct
15 Correct 1288 ms 200220 KB Output is correct
16 Correct 1279 ms 200224 KB Output is correct
17 Correct 1298 ms 200320 KB Output is correct
18 Correct 1067 ms 200340 KB Output is correct
19 Correct 1060 ms 200268 KB Output is correct
20 Correct 1106 ms 200344 KB Output is correct
21 Correct 1068 ms 200448 KB Output is correct
22 Correct 1052 ms 200516 KB Output is correct
23 Correct 1045 ms 200612 KB Output is correct
24 Correct 1036 ms 200612 KB Output is correct
25 Correct 1723 ms 210560 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 187916 KB Output is correct
2 Correct 62 ms 187920 KB Output is correct
3 Correct 111 ms 200396 KB Output is correct
4 Correct 123 ms 200348 KB Output is correct
5 Correct 108 ms 200408 KB Output is correct
6 Correct 111 ms 200312 KB Output is correct
7 Correct 109 ms 200468 KB Output is correct
8 Correct 114 ms 200404 KB Output is correct
9 Correct 113 ms 200580 KB Output is correct
10 Correct 110 ms 200428 KB Output is correct
11 Correct 123 ms 200392 KB Output is correct
12 Correct 110 ms 201948 KB Output is correct
13 Correct 110 ms 201568 KB Output is correct
14 Correct 118 ms 201236 KB Output is correct
15 Correct 125 ms 202072 KB Output is correct
16 Correct 112 ms 202596 KB Output is correct
17 Correct 110 ms 202692 KB Output is correct
18 Correct 115 ms 203100 KB Output is correct
19 Correct 114 ms 206316 KB Output is correct
20 Correct 119 ms 206132 KB Output is correct
21 Correct 115 ms 205916 KB Output is correct
22 Correct 64 ms 187912 KB Output is correct
23 Correct 62 ms 187976 KB Output is correct
24 Correct 62 ms 187928 KB Output is correct
25 Correct 62 ms 187956 KB Output is correct
26 Correct 63 ms 188024 KB Output is correct
27 Correct 62 ms 187980 KB Output is correct
28 Correct 63 ms 187980 KB Output is correct
29 Correct 61 ms 187992 KB Output is correct
30 Correct 60 ms 188052 KB Output is correct
31 Correct 1299 ms 200184 KB Output is correct
32 Correct 1328 ms 200128 KB Output is correct
33 Correct 1296 ms 200192 KB Output is correct
34 Correct 1304 ms 200236 KB Output is correct
35 Correct 1308 ms 200064 KB Output is correct
36 Correct 1125 ms 200196 KB Output is correct
37 Correct 1118 ms 200208 KB Output is correct
38 Correct 1115 ms 200280 KB Output is correct
39 Correct 1112 ms 200152 KB Output is correct
40 Correct 1098 ms 200268 KB Output is correct
41 Correct 1288 ms 200220 KB Output is correct
42 Correct 1279 ms 200224 KB Output is correct
43 Correct 1298 ms 200320 KB Output is correct
44 Correct 1067 ms 200340 KB Output is correct
45 Correct 1060 ms 200268 KB Output is correct
46 Correct 1106 ms 200344 KB Output is correct
47 Correct 1068 ms 200448 KB Output is correct
48 Correct 1052 ms 200516 KB Output is correct
49 Correct 1045 ms 200612 KB Output is correct
50 Correct 1036 ms 200612 KB Output is correct
51 Correct 1723 ms 210560 KB Output is correct
52 Correct 1127 ms 315016 KB Output is correct
53 Correct 1140 ms 315144 KB Output is correct
54 Correct 1080 ms 313092 KB Output is correct
55 Correct 1140 ms 312824 KB Output is correct
56 Correct 1101 ms 313492 KB Output is correct
57 Correct 1117 ms 314868 KB Output is correct
58 Correct 64 ms 187980 KB Output is correct
59 Correct 66 ms 188008 KB Output is correct
60 Correct 66 ms 188008 KB Output is correct
61 Correct 1157 ms 315136 KB Output is correct
62 Correct 1382 ms 315440 KB Output is correct
63 Correct 1237 ms 314016 KB Output is correct
64 Correct 125 ms 201884 KB Output is correct
65 Correct 135 ms 202216 KB Output is correct
66 Correct 1149 ms 315136 KB Output is correct
67 Correct 1109 ms 314892 KB Output is correct
68 Execution timed out 2090 ms 322548 KB Time limit exceeded
69 Halted 0 ms 0 KB -