oj.uz

Submission #795151

# Submission time Handle Problem Language Result Execution time Memory
795151 2023-07-27T07:04:59 Z RushB LOSTIKS (INOI20_lostiks) C++17
59 / 100
 1750 ms 1048576 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];
vector<array<int, 2>> adj[N];
vector<int> key[N];
queue<int> Q[1 << M];


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;
        Q[0].push(label[s]);
        FOR(i, 0, 1 << M) {
                while (Q[i].size()) {
                        int v = Q[i].front();
                        Q[i].pop();
                        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];
                                                Q[nwm].push(u);
                                        }
                                }
                        }
                        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];
                                        Q[i].push(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:80:9: note: in expansion of macro 'FOR'
   80 |         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:83:17: note: in expansion of macro 'FOR'
   83 |                 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:109:25: note: in expansion of macro 'FOR'
  109 |                         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 525 ms 1011728 KB Output is correct
2 Correct 537 ms 1011760 KB Output is correct
3 Correct 623 ms 1033196 KB Output is correct
4 Correct 648 ms 1033148 KB Output is correct
5 Correct 553 ms 1033224 KB Output is correct
6 Correct 542 ms 1033192 KB Output is correct
7 Correct 561 ms 1033300 KB Output is correct
8 Correct 544 ms 1033300 KB Output is correct
9 Correct 523 ms 1033448 KB Output is correct
10 Correct 530 ms 1033300 KB Output is correct
11 Correct 565 ms 1033316 KB Output is correct
12 Correct 590 ms 1034696 KB Output is correct
13 Correct 537 ms 1034260 KB Output is correct
14 Correct 566 ms 1033908 KB Output is correct
15 Correct 565 ms 1034840 KB Output is correct
16 Correct 551 ms 1035528 KB Output is correct
17 Correct 555 ms 1035492 KB Output is correct
18 Correct 543 ms 1036148 KB Output is correct
19 Correct 538 ms 1040180 KB Output is correct
20 Correct 579 ms 1040052 KB Output is correct
21 Correct 562 ms 1039712 KB Output is correct
22 Correct 623 ms 1011812 KB Output is correct
23 Correct 475 ms 1011844 KB Output is correct
24 Correct 509 ms 1011924 KB Output is correct
25 Correct 476 ms 1011812 KB Output is correct
26 Correct 510 ms 1011808 KB Output is correct

Subtask #2
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 1011760 KB Output is correct
2 Correct 495 ms 1011756 KB Output is correct
3 Correct 502 ms 1011812 KB Output is correct
4 Correct 501 ms 1011756 KB Output is correct
5 Correct 494 ms 1013284 KB Output is correct
6 Correct 516 ms 1013292 KB Output is correct
7 Correct 498 ms 1013280 KB Output is correct
8 Correct 508 ms 1013364 KB Output is correct
9 Correct 522 ms 1013296 KB Output is correct
10 Correct 469 ms 1013192 KB Output is correct
11 Correct 483 ms 1013308 KB Output is correct
12 Correct 480 ms 1013248 KB Output is correct
13 Correct 486 ms 1013228 KB Output is correct
14 Correct 482 ms 1013224 KB Output is correct
15 Correct 497 ms 1013284 KB Output is correct
16 Correct 501 ms 1013300 KB Output is correct
17 Correct 486 ms 1013252 KB Output is correct
18 Correct 487 ms 1013432 KB Output is correct
19 Correct 489 ms 1013428 KB Output is correct
20 Correct 482 ms 1013352 KB Output is correct
21 Correct 503 ms 1013572 KB Output is correct
22 Correct 502 ms 1013776 KB Output is correct
23 Correct 480 ms 1013708 KB Output is correct
24 Correct 484 ms 1013656 KB Output is correct
25 Correct 1750 ms 1011788 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 1011728 KB Output is correct
2 Correct 537 ms 1011760 KB Output is correct
3 Correct 623 ms 1033196 KB Output is correct
4 Correct 648 ms 1033148 KB Output is correct
5 Correct 553 ms 1033224 KB Output is correct
6 Correct 542 ms 1033192 KB Output is correct
7 Correct 561 ms 1033300 KB Output is correct
8 Correct 544 ms 1033300 KB Output is correct
9 Correct 523 ms 1033448 KB Output is correct
10 Correct 530 ms 1033300 KB Output is correct
11 Correct 565 ms 1033316 KB Output is correct
12 Correct 590 ms 1034696 KB Output is correct
13 Correct 537 ms 1034260 KB Output is correct
14 Correct 566 ms 1033908 KB Output is correct
15 Correct 565 ms 1034840 KB Output is correct
16 Correct 551 ms 1035528 KB Output is correct
17 Correct 555 ms 1035492 KB Output is correct
18 Correct 543 ms 1036148 KB Output is correct
19 Correct 538 ms 1040180 KB Output is correct
20 Correct 579 ms 1040052 KB Output is correct
21 Correct 562 ms 1039712 KB Output is correct
22 Correct 623 ms 1011812 KB Output is correct
23 Correct 475 ms 1011844 KB Output is correct
24 Correct 509 ms 1011924 KB Output is correct
25 Correct 476 ms 1011812 KB Output is correct
26 Correct 510 ms 1011808 KB Output is correct
27 Correct 480 ms 1011760 KB Output is correct
28 Correct 495 ms 1011756 KB Output is correct
29 Correct 502 ms 1011812 KB Output is correct
30 Correct 501 ms 1011756 KB Output is correct
31 Correct 494 ms 1013284 KB Output is correct
32 Correct 516 ms 1013292 KB Output is correct
33 Correct 498 ms 1013280 KB Output is correct
34 Correct 508 ms 1013364 KB Output is correct
35 Correct 522 ms 1013296 KB Output is correct
36 Correct 469 ms 1013192 KB Output is correct
37 Correct 483 ms 1013308 KB Output is correct
38 Correct 480 ms 1013248 KB Output is correct
39 Correct 486 ms 1013228 KB Output is correct
40 Correct 482 ms 1013224 KB Output is correct
41 Correct 497 ms 1013284 KB Output is correct
42 Correct 501 ms 1013300 KB Output is correct
43 Correct 486 ms 1013252 KB Output is correct
44 Correct 487 ms 1013432 KB Output is correct
45 Correct 489 ms 1013428 KB Output is correct
46 Correct 482 ms 1013352 KB Output is correct
47 Correct 503 ms 1013572 KB Output is correct
48 Correct 502 ms 1013776 KB Output is correct
49 Correct 480 ms 1013708 KB Output is correct
50 Correct 484 ms 1013656 KB Output is correct
51 Correct 1750 ms 1011788 KB Output is correct
52 Runtime error 1495 ms 1048576 KB Execution killed with signal 9
53 Halted 0 ms 0 KB -