oj.uz

Submission #795176

# Submission time Handle Problem Language Result Execution time Memory
795176 2023-07-27T07:18:34 Z RushB LOSTIKS (INOI20_lostiks) C++17
100 / 100
 1855 ms 590044 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
const int64_t INF = 1 << 30;
const int N = 1e6 + 5;
const int NWN = 63;
const int M = 20;
int dist[1 << M][NWN], pr[N][M], msk[N][M], h[N], s, t, U[NWN], V[NWN], label[N], W[NWN][NWN], MSK[NWN][NWN], n;
bool yes[N], seen[NWN];
vector<array<int, 2>> adj[N];
vector<int> key[N];

void dfs(int v, int p) {
        pr[v][0] = p;
        FOR(i, 1, M) {
                pr[v][i] = pr[pr[v][i - 1]][i - 1];
                msk[v][i] = msk[pr[v][i - 1]][i - 1] | msk[v][i - 1];
        }
        for (auto P: adj[v]) {
                int u = P[0], w = P[1];
                if (u == p) continue;
                h[u] = h[v] + 1;
                msk[u][0] = w;
                dfs(u, v);
        }
}
array<int, 2> LCA(int u, int v) {
        int mask = 0;
        if (h[u] > h[v]) swap(u, v);
        for (; h[u] != h[v]; v = pr[v][__lg(h[v] - h[u])])
                mask |= msk[v][__lg(h[v] - h[u])];
        if (u == v)
                return {u, mask};
        for (int i = M - 1; i >= 0; i--) {
                if (pr[v][i] != pr[u][i]) {
                        mask |= msk[v][i];
                        mask |= msk[u][i];
                        v = pr[v][i];
                        u = pr[u][i];
                }
        }
        assert(pr[v][0] == pr[u][0]);
        mask |= msk[u][0];
        mask |= msk[v][0];
        return {pr[v][0], mask};
}

signed main() {
        ios::sync_with_stdio(0), cin.tie(0);
        cin >> n >> s >> t;
        s--;
        t--;
        int E = 0;
        FOR(i, 1, n) {
                int u, v, w, ww = 0;
                cin >> u >> v >> w;
                u--;
                v--;
                w--;
                if (w >= 0) {
                        yes[u] = yes[v] = yes[w] = true;
                        U[E] = u;
                        V[E] = v;
                        ww = 1 << E;
                        key[w].push_back(E);
                        ++E;
                }
                adj[v].push_back({u, ww});
                adj[u].push_back({v, ww});
        }
        dfs(s, s);
        vector<int> node;
        yes[s] = yes[t] = true;
        FOR(i, 0, n) if (yes[i]) 
                node.push_back(i);
        assert(node.size() < NWN);

        FOR(i, 0, node.size()) {
                int u = node[i];
                label[u] = i;
                FOR(j, 0, node.size()) {
                        int v = node[j];
                        auto P = LCA(u, v);
                        W[i][j] = h[u] + h[v] - 2 * h[P[0]];
                        MSK[i][j] = P[1];
                }
        }
        FOR(i, 0, 1 << M) 
                fill(dist[i], dist[i] + NWN, INF);
        dist[0][label[s]] = 0;
        FOR(i, 0, 1 << M) {
                memset(seen, 0, sizeof seen);
                FOR(k, 0, node.size()) {
                        int v = -1;
                        FOR(j, 0, node.size()) if (!seen[j] && (v == -1 || dist[i][j] < dist[i][v]))
                                v = j;
                        seen[v] = true;
                        if (dist[i][v] >= INF)
                                break;
                        for (auto e: key[node[v]]) {
                                int u = (h[U[e]] < h[V[e]] ? U[e] : V[e]);        
                                u = label[u];
                                if ((MSK[v][u] | i) == i) {
                                        int nwm = i | (1 << e);
                                        if (dist[nwm][u] > dist[i][v] + W[u][v]) {
                                                dist[nwm][u] = dist[i][v] + W[u][v];
                                        }
                                }
                        }
                        FOR(u, 0, node.size()) if ((MSK[v][u] | i) == i) {
                                if (dist[i][v] + W[v][u] < dist[i][u]) {
                                        dist[i][u] = dist[i][v] + W[v][u];
                                }
                        }
                }
        }
        int mn = INF;
        FOR(i, 0, 1 << M)
                mn = min(mn, dist[i][label[t]]);
        cout << (mn == INF ? -1 : mn) << '\n';
}
//09:42:20

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
Main.cpp:78:9: note: in expansion of macro 'FOR'
   78 |         FOR(i, 0, node.size()) {
      |         ^~~
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
Main.cpp:81:17: note: in expansion of macro 'FOR'
   81 |                 FOR(j, 0, node.size()) {
      |                 ^~~
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
Main.cpp:93:17: note: in expansion of macro 'FOR'
   93 |                 FOR(k, 0, node.size()) {
      |                 ^~~
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
Main.cpp:95:25: note: in expansion of macro 'FOR'
   95 |                         FOR(j, 0, node.size()) if (!seen[j] && (v == -1 || dist[i][j] < dist[i][v]))
      |                         ^~~
Main.cpp:3:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
Main.cpp:110:25: note: in expansion of macro 'FOR'
  110 |                         FOR(u, 0, node.size()) if ((MSK[v][u] | i) == i) {
      |                         ^~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 305840 KB Output is correct
2 Correct 178 ms 305844 KB Output is correct
3 Correct 283 ms 326224 KB Output is correct
4 Correct 259 ms 327296 KB Output is correct
5 Correct 293 ms 327332 KB Output is correct
6 Correct 266 ms 327296 KB Output is correct
7 Correct 260 ms 327400 KB Output is correct
8 Correct 259 ms 327404 KB Output is correct
9 Correct 320 ms 327592 KB Output is correct
10 Correct 259 ms 327404 KB Output is correct
11 Correct 265 ms 327412 KB Output is correct
12 Correct 275 ms 328804 KB Output is correct
13 Correct 292 ms 328288 KB Output is correct
14 Correct 285 ms 328004 KB Output is correct
15 Correct 344 ms 328904 KB Output is correct
16 Correct 261 ms 329616 KB Output is correct
17 Correct 284 ms 329776 KB Output is correct
18 Correct 307 ms 330256 KB Output is correct
19 Correct 280 ms 334348 KB Output is correct
20 Correct 293 ms 333996 KB Output is correct
21 Correct 275 ms 333824 KB Output is correct
22 Correct 175 ms 305916 KB Output is correct
23 Correct 181 ms 305924 KB Output is correct
24 Correct 219 ms 305920 KB Output is correct
25 Correct 198 ms 305916 KB Output is correct
26 Correct 189 ms 305896 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 305896 KB Output is correct
2 Correct 182 ms 305956 KB Output is correct
3 Correct 233 ms 305900 KB Output is correct
4 Correct 212 ms 305868 KB Output is correct
5 Correct 337 ms 307384 KB Output is correct
6 Correct 319 ms 307396 KB Output is correct
7 Correct 357 ms 307388 KB Output is correct
8 Correct 341 ms 307388 KB Output is correct
9 Correct 336 ms 307400 KB Output is correct
10 Correct 306 ms 307300 KB Output is correct
11 Correct 340 ms 307416 KB Output is correct
12 Correct 325 ms 307412 KB Output is correct
13 Correct 313 ms 307372 KB Output is correct
14 Correct 312 ms 307416 KB Output is correct
15 Correct 336 ms 307348 KB Output is correct
16 Correct 322 ms 307408 KB Output is correct
17 Correct 338 ms 307316 KB Output is correct
18 Correct 314 ms 307540 KB Output is correct
19 Correct 314 ms 307548 KB Output is correct
20 Correct 311 ms 307544 KB Output is correct
21 Correct 315 ms 307704 KB Output is correct
22 Correct 309 ms 307876 KB Output is correct
23 Correct 339 ms 307868 KB Output is correct
24 Correct 311 ms 307888 KB Output is correct
25 Correct 1855 ms 305876 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 305840 KB Output is correct
2 Correct 178 ms 305844 KB Output is correct
3 Correct 283 ms 326224 KB Output is correct
4 Correct 259 ms 327296 KB Output is correct
5 Correct 293 ms 327332 KB Output is correct
6 Correct 266 ms 327296 KB Output is correct
7 Correct 260 ms 327400 KB Output is correct
8 Correct 259 ms 327404 KB Output is correct
9 Correct 320 ms 327592 KB Output is correct
10 Correct 259 ms 327404 KB Output is correct
11 Correct 265 ms 327412 KB Output is correct
12 Correct 275 ms 328804 KB Output is correct
13 Correct 292 ms 328288 KB Output is correct
14 Correct 285 ms 328004 KB Output is correct
15 Correct 344 ms 328904 KB Output is correct
16 Correct 261 ms 329616 KB Output is correct
17 Correct 284 ms 329776 KB Output is correct
18 Correct 307 ms 330256 KB Output is correct
19 Correct 280 ms 334348 KB Output is correct
20 Correct 293 ms 333996 KB Output is correct
21 Correct 275 ms 333824 KB Output is correct
22 Correct 175 ms 305916 KB Output is correct
23 Correct 181 ms 305924 KB Output is correct
24 Correct 219 ms 305920 KB Output is correct
25 Correct 198 ms 305916 KB Output is correct
26 Correct 189 ms 305896 KB Output is correct
27 Correct 175 ms 305896 KB Output is correct
28 Correct 182 ms 305956 KB Output is correct
29 Correct 233 ms 305900 KB Output is correct
30 Correct 212 ms 305868 KB Output is correct
31 Correct 337 ms 307384 KB Output is correct
32 Correct 319 ms 307396 KB Output is correct
33 Correct 357 ms 307388 KB Output is correct
34 Correct 341 ms 307388 KB Output is correct
35 Correct 336 ms 307400 KB Output is correct
36 Correct 306 ms 307300 KB Output is correct
37 Correct 340 ms 307416 KB Output is correct
38 Correct 325 ms 307412 KB Output is correct
39 Correct 313 ms 307372 KB Output is correct
40 Correct 312 ms 307416 KB Output is correct
41 Correct 336 ms 307348 KB Output is correct
42 Correct 322 ms 307408 KB Output is correct
43 Correct 338 ms 307316 KB Output is correct
44 Correct 314 ms 307540 KB Output is correct
45 Correct 314 ms 307548 KB Output is correct
46 Correct 311 ms 307544 KB Output is correct
47 Correct 315 ms 307704 KB Output is correct
48 Correct 309 ms 307876 KB Output is correct
49 Correct 339 ms 307868 KB Output is correct
50 Correct 311 ms 307888 KB Output is correct
51 Correct 1855 ms 305876 KB Output is correct
52 Correct 1397 ms 525188 KB Output is correct
53 Correct 1447 ms 525264 KB Output is correct
54 Correct 1382 ms 522612 KB Output is correct
55 Correct 1387 ms 522448 KB Output is correct
56 Correct 1563 ms 523324 KB Output is correct
57 Correct 1412 ms 524988 KB Output is correct
58 Correct 182 ms 305796 KB Output is correct
59 Correct 190 ms 305816 KB Output is correct
60 Correct 181 ms 305864 KB Output is correct
61 Correct 1433 ms 525144 KB Output is correct
62 Correct 1449 ms 522360 KB Output is correct
63 Correct 1492 ms 522376 KB Output is correct
64 Correct 315 ms 329244 KB Output is correct
65 Correct 310 ms 329464 KB Output is correct
66 Correct 1430 ms 525308 KB Output is correct
67 Correct 1406 ms 525052 KB Output is correct
68 Correct 1334 ms 520712 KB Output is correct
69 Correct 1346 ms 521232 KB Output is correct
70 Correct 1283 ms 520468 KB Output is correct
71 Correct 1248 ms 520468 KB Output is correct
72 Correct 1269 ms 520504 KB Output is correct
73 Correct 1267 ms 522020 KB Output is correct
74 Correct 1324 ms 522824 KB Output is correct
75 Correct 1375 ms 522572 KB Output is correct
76 Correct 1342 ms 523488 KB Output is correct
77 Correct 1280 ms 522200 KB Output is correct
78 Correct 1523 ms 525080 KB Output is correct
79 Correct 1530 ms 524764 KB Output is correct
80 Correct 1494 ms 523224 KB Output is correct
81 Correct 1642 ms 539636 KB Output is correct
82 Correct 1623 ms 541196 KB Output is correct
83 Correct 1678 ms 541048 KB Output is correct
84 Correct 1748 ms 552176 KB Output is correct
85 Correct 1834 ms 590044 KB Output is correct
86 Correct 1823 ms 589124 KB Output is correct
87 Correct 1732 ms 589108 KB Output is correct