oj.uz

Submission #467810

# Submission time Handle Problem Language Result Execution time Memory
467810 2021-08-24T17:44:42 Z spike1236 Evacuation plan (IZhO18_plan) C++14
100 / 100
 648 ms 53016 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define ld long double
#define all(_v) _v.begin(), _v.end()
#define sz(_v) (int)_v.size()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define veci vector <int>
#define vecll vector <ll>

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.1415926535897932384626433832795;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

const int MAXN = 1e5 + 10;
int n, m, k;
vector <pii> g[MAXN];
ll d[MAXN];
int up[MAXN][20];
ll mn[MAXN][20];
int tin[MAXN], tout[MAXN], tmr;

void dfs(int v, int p) {
    mn[v][0] = d[v];
    up[v][0] = p;
    for(int i = 1; i < 18; ++i) {
        if(up[v][i - 1]) {
            up[v][i] = up[up[v][i - 1]][i - 1];
            mn[v][i] = min(mn[up[v][i - 1]][i - 1], mn[v][i - 1]);
        }
    }
    tin[v] = ++tmr;
    for(auto to : g[v]) if(to.f != p) dfs(to.f, v);
    tout[v] = ++tmr;
}

bool upper(int v, int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}

int lca_(int v, int u) {
    if(upper(v, u)) return v;
    if(upper(u, v)) return u;
    for(int i = 17; i >= 0; --i)
        if(up[v][i] && !upper(up[v][i], u)) v = up[v][i];
    return up[v][0];
}

ll get_mn(int v, int lca) {
    if(v == lca) return d[v];
    assert(upper(lca, v));
    ll res = 1e18;
    for(int i = 17; i >= 0; --i) {
        if(up[v][i] && !upper(up[v][i], lca)) {
            res = min(res, mn[v][i]);
            v = up[v][i];
        }
    }
    return min(res, mn[v][0]);
}

int par[MAXN];

int get(int v) {
    return (v == par[v] ? v : par[v] = get(par[v]));
}

bool unite(int v, int u) {
    v = get(v), u = get(u);
    if(v == u) return 0;
    if(rand() & 1) par[v] = u;
    else par[u] = v;
    return 1;
}

void solve() {
    cin >> n >> m;
    vector <pii> ed;
    for(int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        ed.pb(mp(u, v));
        g[u].pb(mp(v, w));
        g[v].pb(mp(u, w));
    }
    for(int i = 1; i <= n; ++i) d[i] = 1e18;
    cin >> k;
    priority_queue <pair <ll, int> > q;
    for(int i = 1, v; i <= k; ++i) {
        cin >> v;
        q.push(mp(0ll, v));
        d[v] = 0;
    }
    while(!q.empty()) {
        auto v = q.top();
        q.pop();
        v.f = -v.f;
        if(v.f != d[v.s]) continue;
        for(auto to : g[v.s]) {
            if(d[to.f] > v.f + to.s) {
                d[to.f] = v.f + to.s;
                q.push(mp(-d[to.f], to.f));
            }
        }
    }
    sort(all(ed), [](const pii &a, const pii &b) {return (min(d[a.f], d[a.s]) < min(d[b.f], d[b.s]));});
    reverse(all(ed));
    for(int i = 0; i <= n; ++i) {
        par[i] = i;
        for(int j = 0; j < 18; ++j) mn[i][j] = 1e18;
        g[i].clear();
    }
    for(auto it : ed) {
        if(unite(it.f, it.s)) {
            g[it.f].pb(mp(it.s, 0));
            g[it.s].pb(mp(it.f, 0));
        }
    }
    dfs(1, 0);
    cin >> k;
    for(int cs = 1, u, v; cs <= k; ++cs) {
        cin >> u >> v;
        int LCA = lca_(u, v);
        cout << min({get_mn(u, LCA), get_mn(v, LCA), d[LCA]}) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int CNT_TESTS = 1;
    ///cin >> CNT_TESTS;
    for(int NUMCASE = 1; NUMCASE <= CNT_TESTS; ++NUMCASE) {
        solve();
        if(NUMCASE != CNT_TESTS) cout << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2960 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 3020 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 3 ms 3020 KB Output is correct
11 Correct 3 ms 3020 KB Output is correct
12 Correct 3 ms 3020 KB Output is correct
13 Correct 3 ms 2892 KB Output is correct
14 Correct 3 ms 2892 KB Output is correct
15 Correct 3 ms 2892 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2960 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 3020 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 3 ms 3020 KB Output is correct
11 Correct 3 ms 3020 KB Output is correct
12 Correct 3 ms 3020 KB Output is correct
13 Correct 3 ms 2892 KB Output is correct
14 Correct 3 ms 2892 KB Output is correct
15 Correct 3 ms 2892 KB Output is correct
16 Correct 203 ms 28152 KB Output is correct
17 Correct 585 ms 50552 KB Output is correct
18 Correct 37 ms 7880 KB Output is correct
19 Correct 190 ms 34960 KB Output is correct
20 Correct 579 ms 50456 KB Output is correct
21 Correct 317 ms 37568 KB Output is correct
22 Correct 212 ms 37544 KB Output is correct
23 Correct 565 ms 50432 KB Output is correct
24 Correct 561 ms 50348 KB Output is correct
25 Correct 590 ms 50392 KB Output is correct
26 Correct 196 ms 34624 KB Output is correct
27 Correct 166 ms 34740 KB Output is correct
28 Correct 166 ms 34716 KB Output is correct
29 Correct 176 ms 34756 KB Output is correct
30 Correct 169 ms 34904 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2676 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 37920 KB Output is correct
2 Correct 502 ms 50100 KB Output is correct
3 Correct 490 ms 50144 KB Output is correct
4 Correct 140 ms 34868 KB Output is correct
5 Correct 487 ms 50000 KB Output is correct
6 Correct 513 ms 50000 KB Output is correct
7 Correct 531 ms 50240 KB Output is correct
8 Correct 469 ms 50044 KB Output is correct
9 Correct 485 ms 50224 KB Output is correct
10 Correct 497 ms 50000 KB Output is correct
11 Correct 498 ms 50060 KB Output is correct
12 Correct 510 ms 50088 KB Output is correct
13 Correct 506 ms 50040 KB Output is correct
14 Correct 542 ms 50048 KB Output is correct
15 Correct 468 ms 48160 KB Output is correct
16 Correct 497 ms 50180 KB Output is correct
17 Correct 475 ms 49996 KB Output is correct
18 Correct 499 ms 49960 KB Output is correct
19 Correct 134 ms 36376 KB Output is correct
20 Correct 488 ms 50048 KB Output is correct
21 Correct 470 ms 49472 KB Output is correct
22 Correct 111 ms 34468 KB Output is correct
23 Correct 125 ms 33820 KB Output is correct
24 Correct 117 ms 35292 KB Output is correct
25 Correct 120 ms 35364 KB Output is correct
26 Correct 140 ms 34228 KB Output is correct
27 Correct 143 ms 36964 KB Output is correct
28 Correct 113 ms 35112 KB Output is correct
29 Correct 147 ms 36368 KB Output is correct
30 Correct 127 ms 35168 KB Output is correct
31 Correct 139 ms 36272 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2960 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 3020 KB Output is correct
6 Correct 3 ms 3020 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 3 ms 2892 KB Output is correct
10 Correct 3 ms 3020 KB Output is correct
11 Correct 3 ms 3020 KB Output is correct
12 Correct 3 ms 3020 KB Output is correct
13 Correct 3 ms 2892 KB Output is correct
14 Correct 3 ms 2892 KB Output is correct
15 Correct 3 ms 2892 KB Output is correct
16 Correct 203 ms 28152 KB Output is correct
17 Correct 585 ms 50552 KB Output is correct
18 Correct 37 ms 7880 KB Output is correct
19 Correct 190 ms 34960 KB Output is correct
20 Correct 579 ms 50456 KB Output is correct
21 Correct 317 ms 37568 KB Output is correct
22 Correct 212 ms 37544 KB Output is correct
23 Correct 565 ms 50432 KB Output is correct
24 Correct 561 ms 50348 KB Output is correct
25 Correct 590 ms 50392 KB Output is correct
26 Correct 196 ms 34624 KB Output is correct
27 Correct 166 ms 34740 KB Output is correct
28 Correct 166 ms 34716 KB Output is correct
29 Correct 176 ms 34756 KB Output is correct
30 Correct 169 ms 34904 KB Output is correct
31 Correct 2 ms 2636 KB Output is correct
32 Correct 2 ms 2636 KB Output is correct
33 Correct 2 ms 2668 KB Output is correct
34 Correct 2 ms 2636 KB Output is correct
35 Correct 2 ms 2636 KB Output is correct
36 Correct 2 ms 2636 KB Output is correct
37 Correct 2 ms 2636 KB Output is correct
38 Correct 2 ms 2636 KB Output is correct
39 Correct 2 ms 2676 KB Output is correct
40 Correct 2 ms 2636 KB Output is correct
41 Correct 258 ms 37920 KB Output is correct
42 Correct 502 ms 50100 KB Output is correct
43 Correct 490 ms 50144 KB Output is correct
44 Correct 140 ms 34868 KB Output is correct
45 Correct 487 ms 50000 KB Output is correct
46 Correct 513 ms 50000 KB Output is correct
47 Correct 531 ms 50240 KB Output is correct
48 Correct 469 ms 50044 KB Output is correct
49 Correct 485 ms 50224 KB Output is correct
50 Correct 497 ms 50000 KB Output is correct
51 Correct 498 ms 50060 KB Output is correct
52 Correct 510 ms 50088 KB Output is correct
53 Correct 506 ms 50040 KB Output is correct
54 Correct 542 ms 50048 KB Output is correct
55 Correct 468 ms 48160 KB Output is correct
56 Correct 497 ms 50180 KB Output is correct
57 Correct 475 ms 49996 KB Output is correct
58 Correct 499 ms 49960 KB Output is correct
59 Correct 134 ms 36376 KB Output is correct
60 Correct 488 ms 50048 KB Output is correct
61 Correct 470 ms 49472 KB Output is correct
62 Correct 111 ms 34468 KB Output is correct
63 Correct 125 ms 33820 KB Output is correct
64 Correct 117 ms 35292 KB Output is correct
65 Correct 120 ms 35364 KB Output is correct
66 Correct 140 ms 34228 KB Output is correct
67 Correct 143 ms 36964 KB Output is correct
68 Correct 113 ms 35112 KB Output is correct
69 Correct 147 ms 36368 KB Output is correct
70 Correct 127 ms 35168 KB Output is correct
71 Correct 139 ms 36272 KB Output is correct
72 Correct 352 ms 40940 KB Output is correct
73 Correct 639 ms 52824 KB Output is correct
74 Correct 600 ms 52948 KB Output is correct
75 Correct 618 ms 52860 KB Output is correct
76 Correct 648 ms 52860 KB Output is correct
77 Correct 585 ms 52896 KB Output is correct
78 Correct 633 ms 52836 KB Output is correct
79 Correct 625 ms 52868 KB Output is correct
80 Correct 588 ms 53016 KB Output is correct
81 Correct 573 ms 52756 KB Output is correct
82 Correct 579 ms 52812 KB Output is correct
83 Correct 614 ms 52736 KB Output is correct
84 Correct 629 ms 52648 KB Output is correct
85 Correct 572 ms 50644 KB Output is correct
86 Correct 598 ms 52596 KB Output is correct
87 Correct 584 ms 52640 KB Output is correct
88 Correct 582 ms 52812 KB Output is correct
89 Correct 300 ms 38632 KB Output is correct
90 Correct 575 ms 52588 KB Output is correct
91 Correct 612 ms 51924 KB Output is correct
92 Correct 184 ms 36760 KB Output is correct
93 Correct 260 ms 35916 KB Output is correct
94 Correct 186 ms 36704 KB Output is correct
95 Correct 186 ms 36852 KB Output is correct
96 Correct 259 ms 35672 KB Output is correct
97 Correct 287 ms 37552 KB Output is correct
98 Correct 183 ms 36560 KB Output is correct
99 Correct 290 ms 38652 KB Output is correct
100 Correct 192 ms 36636 KB Output is correct