oj.uz

Submission #773630

# Submission time Handle Problem Language Result Execution time Memory
773630 2023-07-05T07:23:36 Z ParsaS LOSTIKS (INOI20_lostiks) C++17
59 / 100
 2000 ms 515040 KB 
// In the name of God
#pragma GCC optimize("O2")
#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 = 21;
int n, c, s, t;
vector<int> adj[N];
vector<pair<int, int> > E;
int f[N], tin[N], tout[N], T, h[N];
int dis[lg][N];
ll dp[1 << lg][lg];
bool ok[1 << lg][lg];

void dfs(int v, int p) {
    tin[v] = ++T;
    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);
        }
    }
}
inline bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[v] >= tout[u];
}

void solve() {
    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));
    }

    dfs(s, 0);
    tout[0] = ++T;

    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);
        queue<int> q;
        q.push(E[i].fi);
        dis[i][E[i].fi] = 0;
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto u : adj[v]) {
                if (dis[i][u] > dis[i][v] + 1) {
                    dis[i][u] = dis[i][v] + 1;
                    q.push(u);
                }
            }
        }
    }
    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[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[i]] + dis[i][f[i]]);
                    }
                }
            }

            if (ok[mask][c]) {
                ans = min(ans, dp[mask][i] + dis[i][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 151 ms 450732 KB Output is correct
2 Correct 156 ms 450724 KB Output is correct
3 Correct 184 ms 455260 KB Output is correct
4 Correct 179 ms 455264 KB Output is correct
5 Correct 207 ms 455284 KB Output is correct
6 Correct 219 ms 455288 KB Output is correct
7 Correct 179 ms 455336 KB Output is correct
8 Correct 190 ms 455428 KB Output is correct
9 Correct 183 ms 455500 KB Output is correct
10 Correct 183 ms 455348 KB Output is correct
11 Correct 187 ms 455500 KB Output is correct
12 Correct 180 ms 456856 KB Output is correct
13 Correct 176 ms 456572 KB Output is correct
14 Correct 176 ms 456208 KB Output is correct
15 Correct 182 ms 456968 KB Output is correct
16 Correct 182 ms 457592 KB Output is correct
17 Correct 178 ms 457536 KB Output is correct
18 Correct 177 ms 457880 KB Output is correct
19 Correct 180 ms 461100 KB Output is correct
20 Correct 180 ms 461016 KB Output is correct
21 Correct 183 ms 460876 KB Output is correct
22 Correct 139 ms 450788 KB Output is correct
23 Correct 138 ms 450764 KB Output is correct
24 Correct 138 ms 450764 KB Output is correct
25 Correct 136 ms 450676 KB Output is correct
26 Correct 139 ms 450752 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 450684 KB Output is correct
2 Correct 136 ms 450780 KB Output is correct
3 Correct 135 ms 450672 KB Output is correct
4 Correct 137 ms 450704 KB Output is correct
5 Correct 1346 ms 461852 KB Output is correct
6 Correct 1349 ms 461848 KB Output is correct
7 Correct 1322 ms 461872 KB Output is correct
8 Correct 1361 ms 461856 KB Output is correct
9 Correct 1362 ms 461848 KB Output is correct
10 Correct 1175 ms 461936 KB Output is correct
11 Correct 1214 ms 461864 KB Output is correct
12 Correct 1183 ms 461872 KB Output is correct
13 Correct 1180 ms 462060 KB Output is correct
14 Correct 1149 ms 461904 KB Output is correct
15 Correct 1289 ms 461792 KB Output is correct
16 Correct 1294 ms 461884 KB Output is correct
17 Correct 1308 ms 461804 KB Output is correct
18 Correct 1167 ms 461904 KB Output is correct
19 Correct 1130 ms 461916 KB Output is correct
20 Correct 1161 ms 461880 KB Output is correct
21 Correct 1094 ms 462032 KB Output is correct
22 Correct 1072 ms 462268 KB Output is correct
23 Correct 1066 ms 462264 KB Output is correct
24 Correct 1107 ms 462196 KB Output is correct
25 Correct 1733 ms 472344 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 450732 KB Output is correct
2 Correct 156 ms 450724 KB Output is correct
3 Correct 184 ms 455260 KB Output is correct
4 Correct 179 ms 455264 KB Output is correct
5 Correct 207 ms 455284 KB Output is correct
6 Correct 219 ms 455288 KB Output is correct
7 Correct 179 ms 455336 KB Output is correct
8 Correct 190 ms 455428 KB Output is correct
9 Correct 183 ms 455500 KB Output is correct
10 Correct 183 ms 455348 KB Output is correct
11 Correct 187 ms 455500 KB Output is correct
12 Correct 180 ms 456856 KB Output is correct
13 Correct 176 ms 456572 KB Output is correct
14 Correct 176 ms 456208 KB Output is correct
15 Correct 182 ms 456968 KB Output is correct
16 Correct 182 ms 457592 KB Output is correct
17 Correct 178 ms 457536 KB Output is correct
18 Correct 177 ms 457880 KB Output is correct
19 Correct 180 ms 461100 KB Output is correct
20 Correct 180 ms 461016 KB Output is correct
21 Correct 183 ms 460876 KB Output is correct
22 Correct 139 ms 450788 KB Output is correct
23 Correct 138 ms 450764 KB Output is correct
24 Correct 138 ms 450764 KB Output is correct
25 Correct 136 ms 450676 KB Output is correct
26 Correct 139 ms 450752 KB Output is correct
27 Correct 158 ms 450684 KB Output is correct
28 Correct 136 ms 450780 KB Output is correct
29 Correct 135 ms 450672 KB Output is correct
30 Correct 137 ms 450704 KB Output is correct
31 Correct 1346 ms 461852 KB Output is correct
32 Correct 1349 ms 461848 KB Output is correct
33 Correct 1322 ms 461872 KB Output is correct
34 Correct 1361 ms 461856 KB Output is correct
35 Correct 1362 ms 461848 KB Output is correct
36 Correct 1175 ms 461936 KB Output is correct
37 Correct 1214 ms 461864 KB Output is correct
38 Correct 1183 ms 461872 KB Output is correct
39 Correct 1180 ms 462060 KB Output is correct
40 Correct 1149 ms 461904 KB Output is correct
41 Correct 1289 ms 461792 KB Output is correct
42 Correct 1294 ms 461884 KB Output is correct
43 Correct 1308 ms 461804 KB Output is correct
44 Correct 1167 ms 461904 KB Output is correct
45 Correct 1130 ms 461916 KB Output is correct
46 Correct 1161 ms 461880 KB Output is correct
47 Correct 1094 ms 462032 KB Output is correct
48 Correct 1072 ms 462268 KB Output is correct
49 Correct 1066 ms 462264 KB Output is correct
50 Correct 1107 ms 462196 KB Output is correct
51 Correct 1733 ms 472344 KB Output is correct
52 Correct 1646 ms 499484 KB Output is correct
53 Correct 1814 ms 499444 KB Output is correct
54 Correct 1926 ms 512952 KB Output is correct
55 Correct 1386 ms 512644 KB Output is correct
56 Correct 1790 ms 513412 KB Output is correct
57 Correct 1765 ms 514760 KB Output is correct
58 Correct 134 ms 450764 KB Output is correct
59 Correct 137 ms 450776 KB Output is correct
60 Correct 138 ms 450748 KB Output is correct
61 Correct 1150 ms 515040 KB Output is correct
62 Execution timed out 2072 ms 167684 KB Time limit exceeded
63 Halted 0 ms 0 KB -