oj.uz

Submission #940734

# Submission time Handle Problem Language Result Execution time Memory
940734 2024-03-07T14:32:47 Z KK_1729 Evacuation plan (IZhO18_plan) C++17
100 / 100
 1159 ms 108712 KB 
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}

int N = 0;
vector<vector<pair<int, int>>> graph;
vector<int> distance(vector<int> source){
    // return ;
    using T = pair<long long, int>;
	priority_queue<T, vector<T>, greater<T>> pq; // stores dist, node
 
    vector<int> dist(N+1, 1e9);
    
 
    for (auto x: source){
        pq.push({0, x});
        dist[x] = 0;
    }
 
    while (!pq.empty()){
        auto [cdist, node] = pq.top();
 
        pq.pop();
        if (cdist != dist[node]) continue;
        for (auto x: graph[node]){
            if (cdist + x.second < dist[x.first]){
                pq.push({dist[x.first] = cdist + x.second, x.first});
            }
        }
    }
    return dist;
}


struct UFDS {
    vector<int> link, siz;
    UFDS(int n) : link(n), siz(n, 1) { iota(link.begin(), link.end(), 0); } //each element as its own subset, with size 1
    int findRoot(int x) {
        return x == link[x]  ? x : link[x]  =  findRoot(link[x]);  
    }
    bool same(int x, int y) { return findRoot(x) == findRoot(y); }
    bool unite(int x, int y) {
        x = findRoot(x);
        y = findRoot(y);
        if (x == y)
            return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        link[y] = x;
        return true;
    }
    int size(int x) { return siz[findRoot(x)]; }
};
int min(int x, int y){
    if (x < y) return x;
    else return y;
}
vector<vector<pair<int, int>>> maxtree;
vector<int> up(N+1);
int L = 0;
vector<vector<int>> bin;
vector<vector<int>> mbin;
vector<int> depth;

int lca(int a, int b){
    if (depth[a] < depth[b]) swap(a, b);
    int k = depth[a]-depth[b];
    for (int j = L-1; j >= 0; j--){
        if (k & (1 << j)) a = bin[a][j];
    }
    if (a == b) return a;
    for (int j = L-1; j >= 0; j--){
        if (bin[a][j] != bin[b][j]){
            a = bin[a][j];
            b = bin[b][j];
        }
    }
    return bin[a][0];
}
void solve(){
    int n, m; cin >> n >> m;
    N = n;
    graph.resize(n+1);

    FOR(i,0,m){
        int a, b, w; cin >> a >> b >> w;
        graph[a].pb({b, w});
        graph[b].pb({a, w});
    }

    int k; cin >> k;
    vector<int> np(k);
    FOR(i,0,k) cin >> np[i];

    vector<int> d = distance(np);

    vector<vector<int>> new_graph(n+1);
    vector<vector<int>> edges;
    FOR(i,1,n+1){
        for (auto x: graph[i]){
            edges.pb({min(d[x.first], d[i]), i, x.first});
        }
    }

    UFDS ds(n+1);
    sort(all(edges));
    reverse(all(edges));
    


    maxtree.resize(n+1);
    for (auto edge: edges){
        // printVector(edge);
        if (!ds.same(edge[1], edge[2])){
            // cout << edge[1] << " " << edge[2] << " " << edge[0] << endl;
            ds.unite(edge[1], edge[2]);
            maxtree[edge[1]].pb({edge[2], edge[0]});
            maxtree[edge[2]].pb({edge[1], edge[0]});
        }
    }
    // FOR(i,1,n+1){
    //     for (auto x: maxtree[i]) cout << x.first << x.second << endl;
    //     cout << endl;
    // }
    L = log2(n)+1;
    bin.resize(n+1, vector<int>(L+1));
    mbin.resize(n+1, vector<int>(L+1));
    depth.resize(n+1);
    stack<int> s;
    s.push(1);
    vector<int> vis(n+1);
    bin[1][0] = 1;
    depth[1] = 1;
    while (!s.empty()){
        int current = s.top();
        s.pop();
        if (vis[current]) continue;
        for (auto x: maxtree[current]){
            if (vis[x.first]) continue;
            bin[x.first][0] = current;
            mbin[x.first][0] = x.second;
            depth[x.first] = depth[current]+1;
            s.push(x.first);
        }
        vis[current] = 1;
    }
    for (int i = 1; i <= L; ++i){
        for (int j = 1; j <= n; ++j){
            bin[j][i] = bin[ bin[j][i-1] ][i-1];
            mbin[j][i] = min(mbin[j][i-1], mbin[ bin[j][i-1] ][i-1]);
        }
    }
    int q; cin >> q;
    while (q--){

        int a, b; cin >> a >> b;
        int l = lca(a, b);
        int k = depth[a]-depth[l];
        int ans = 1e9;
        for (int i = L; i >= 0; i--){
            if (k & (1 << i)){
                ans = min(ans, mbin[a][i]);
                a = bin[a][i];
            }
        }
        k = depth[b]-depth[l];
        for (int i = L; i >= 0; i--){
            if (k & (1 << i)){
                ans = min(ans, mbin[b][i]);
                b = bin[b][i];
            }
        }
        cout << ans << endl;
    }
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int t = 1; // cin >> t;
    while (t--) solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 936 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 2 ms 856 KB Output is correct
14 Correct 1 ms 732 KB Output is correct
15 Correct 2 ms 860 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 936 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 2 ms 856 KB Output is correct
14 Correct 1 ms 732 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 245 ms 43556 KB Output is correct
17 Correct 989 ms 107364 KB Output is correct
18 Correct 42 ms 10896 KB Output is correct
19 Correct 192 ms 51764 KB Output is correct
20 Correct 991 ms 107308 KB Output is correct
21 Correct 341 ms 65124 KB Output is correct
22 Correct 278 ms 49492 KB Output is correct
23 Correct 874 ms 106244 KB Output is correct
24 Correct 1031 ms 107264 KB Output is correct
25 Correct 1159 ms 108712 KB Output is correct
26 Correct 218 ms 51700 KB Output is correct
27 Correct 209 ms 52128 KB Output is correct
28 Correct 225 ms 52528 KB Output is correct
29 Correct 210 ms 52852 KB Output is correct
30 Correct 185 ms 51736 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 756 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 65104 KB Output is correct
2 Correct 868 ms 107488 KB Output is correct
3 Correct 922 ms 107276 KB Output is correct
4 Correct 211 ms 48920 KB Output is correct
5 Correct 840 ms 107992 KB Output is correct
6 Correct 779 ms 107772 KB Output is correct
7 Correct 804 ms 107408 KB Output is correct
8 Correct 832 ms 108284 KB Output is correct
9 Correct 805 ms 107340 KB Output is correct
10 Correct 800 ms 107464 KB Output is correct
11 Correct 790 ms 107664 KB Output is correct
12 Correct 810 ms 105352 KB Output is correct
13 Correct 796 ms 105468 KB Output is correct
14 Correct 758 ms 106036 KB Output is correct
15 Correct 820 ms 105216 KB Output is correct
16 Correct 825 ms 106168 KB Output is correct
17 Correct 773 ms 105220 KB Output is correct
18 Correct 804 ms 105476 KB Output is correct
19 Correct 190 ms 49148 KB Output is correct
20 Correct 778 ms 106504 KB Output is correct
21 Correct 486 ms 105912 KB Output is correct
22 Correct 128 ms 50628 KB Output is correct
23 Correct 179 ms 49008 KB Output is correct
24 Correct 128 ms 50476 KB Output is correct
25 Correct 127 ms 49984 KB Output is correct
26 Correct 179 ms 48900 KB Output is correct
27 Correct 186 ms 49228 KB Output is correct
28 Correct 147 ms 51280 KB Output is correct
29 Correct 185 ms 47936 KB Output is correct
30 Correct 125 ms 50720 KB Output is correct
31 Correct 203 ms 48016 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 936 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 2 ms 856 KB Output is correct
14 Correct 1 ms 732 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 245 ms 43556 KB Output is correct
17 Correct 989 ms 107364 KB Output is correct
18 Correct 42 ms 10896 KB Output is correct
19 Correct 192 ms 51764 KB Output is correct
20 Correct 991 ms 107308 KB Output is correct
21 Correct 341 ms 65124 KB Output is correct
22 Correct 278 ms 49492 KB Output is correct
23 Correct 874 ms 106244 KB Output is correct
24 Correct 1031 ms 107264 KB Output is correct
25 Correct 1159 ms 108712 KB Output is correct
26 Correct 218 ms 51700 KB Output is correct
27 Correct 209 ms 52128 KB Output is correct
28 Correct 225 ms 52528 KB Output is correct
29 Correct 210 ms 52852 KB Output is correct
30 Correct 185 ms 51736 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 1 ms 604 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 756 KB Output is correct
41 Correct 401 ms 65104 KB Output is correct
42 Correct 868 ms 107488 KB Output is correct
43 Correct 922 ms 107276 KB Output is correct
44 Correct 211 ms 48920 KB Output is correct
45 Correct 840 ms 107992 KB Output is correct
46 Correct 779 ms 107772 KB Output is correct
47 Correct 804 ms 107408 KB Output is correct
48 Correct 832 ms 108284 KB Output is correct
49 Correct 805 ms 107340 KB Output is correct
50 Correct 800 ms 107464 KB Output is correct
51 Correct 790 ms 107664 KB Output is correct
52 Correct 810 ms 105352 KB Output is correct
53 Correct 796 ms 105468 KB Output is correct
54 Correct 758 ms 106036 KB Output is correct
55 Correct 820 ms 105216 KB Output is correct
56 Correct 825 ms 106168 KB Output is correct
57 Correct 773 ms 105220 KB Output is correct
58 Correct 804 ms 105476 KB Output is correct
59 Correct 190 ms 49148 KB Output is correct
60 Correct 778 ms 106504 KB Output is correct
61 Correct 486 ms 105912 KB Output is correct
62 Correct 128 ms 50628 KB Output is correct
63 Correct 179 ms 49008 KB Output is correct
64 Correct 128 ms 50476 KB Output is correct
65 Correct 127 ms 49984 KB Output is correct
66 Correct 179 ms 48900 KB Output is correct
67 Correct 186 ms 49228 KB Output is correct
68 Correct 147 ms 51280 KB Output is correct
69 Correct 185 ms 47936 KB Output is correct
70 Correct 125 ms 50720 KB Output is correct
71 Correct 203 ms 48016 KB Output is correct
72 Correct 433 ms 64340 KB Output is correct
73 Correct 907 ms 106624 KB Output is correct
74 Correct 854 ms 107272 KB Output is correct
75 Correct 894 ms 106176 KB Output is correct
76 Correct 909 ms 106196 KB Output is correct
77 Correct 830 ms 106208 KB Output is correct
78 Correct 844 ms 107284 KB Output is correct
79 Correct 844 ms 106796 KB Output is correct
80 Correct 874 ms 106220 KB Output is correct
81 Correct 870 ms 107000 KB Output is correct
82 Correct 882 ms 107256 KB Output is correct
83 Correct 879 ms 106764 KB Output is correct
84 Correct 876 ms 106540 KB Output is correct
85 Correct 860 ms 106288 KB Output is correct
86 Correct 895 ms 106436 KB Output is correct
87 Correct 832 ms 107136 KB Output is correct
88 Correct 901 ms 107264 KB Output is correct
89 Correct 330 ms 50424 KB Output is correct
90 Correct 880 ms 106148 KB Output is correct
91 Correct 582 ms 106712 KB Output is correct
92 Correct 187 ms 51336 KB Output is correct
93 Correct 260 ms 50876 KB Output is correct
94 Correct 202 ms 52036 KB Output is correct
95 Correct 193 ms 51496 KB Output is correct
96 Correct 268 ms 50096 KB Output is correct
97 Correct 328 ms 49884 KB Output is correct
98 Correct 211 ms 51252 KB Output is correct
99 Correct 312 ms 49416 KB Output is correct
100 Correct 187 ms 51644 KB Output is correct