oj.uz

답안 #940537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
940537 2024-03-07T10:20:45 Z KK_1729 Evacuation plan (IZhO18_plan) C++17
41 / 100
 4000 ms 103844 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, 1e16);
    
 
    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;
}

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));
    vector<vector<pair<int, int>>> maxtree(n+1);
    for (auto edge: edges){
        // printVector(edge);
        if (!ds.same(edge[1], edge[2])){
            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;
    // }
    int q; cin >> q;
    while (q--){
        int a, b; cin >> a >> b;
        stack<pair<int, int>> s;
        s.push({a, 1e11});
        vector<int> visited(n+1);
        while (!s.empty()){
            pair<int, int> current = s.top();
            s.pop();
            if (current.first == b){
                cout << current.second << endl;
                break;
            }
            if (visited[current.first]) continue;
            for (auto x: maxtree[current.first]){
                if (visited[x.first]) continue;
                s.push({x.first, min(current.second, x.second)});
                
            }
            visited[current.first] = 1;
        }
    }
}
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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 8 ms 600 KB Output is correct
3 Correct 8 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 8 ms 604 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 9 ms 804 KB Output is correct
10 Correct 11 ms 604 KB Output is correct
11 Correct 10 ms 604 KB Output is correct
12 Correct 10 ms 856 KB Output is correct
13 Correct 9 ms 604 KB Output is correct
14 Correct 10 ms 604 KB Output is correct
15 Correct 15 ms 604 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 8 ms 600 KB Output is correct
3 Correct 8 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 8 ms 604 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 9 ms 804 KB Output is correct
10 Correct 11 ms 604 KB Output is correct
11 Correct 10 ms 604 KB Output is correct
12 Correct 10 ms 856 KB Output is correct
13 Correct 9 ms 604 KB Output is correct
14 Correct 10 ms 604 KB Output is correct
15 Correct 15 ms 604 KB Output is correct
16 Execution timed out 4040 ms 31132 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 456 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 350 ms 47384 KB Output is correct
2 Correct 874 ms 101896 KB Output is correct
3 Correct 817 ms 101872 KB Output is correct
4 Correct 124 ms 32692 KB Output is correct
5 Correct 865 ms 102588 KB Output is correct
6 Correct 903 ms 101908 KB Output is correct
7 Correct 877 ms 102052 KB Output is correct
8 Correct 851 ms 101884 KB Output is correct
9 Correct 790 ms 101928 KB Output is correct
10 Correct 802 ms 101860 KB Output is correct
11 Correct 902 ms 102400 KB Output is correct
12 Correct 784 ms 102528 KB Output is correct
13 Correct 856 ms 101808 KB Output is correct
14 Correct 927 ms 101972 KB Output is correct
15 Correct 796 ms 103096 KB Output is correct
16 Correct 802 ms 102392 KB Output is correct
17 Correct 867 ms 102396 KB Output is correct
18 Correct 790 ms 101876 KB Output is correct
19 Correct 120 ms 32500 KB Output is correct
20 Correct 782 ms 101928 KB Output is correct
21 Correct 509 ms 103844 KB Output is correct
22 Correct 99 ms 35056 KB Output is correct
23 Correct 127 ms 33888 KB Output is correct
24 Correct 101 ms 34344 KB Output is correct
25 Correct 117 ms 35172 KB Output is correct
26 Correct 139 ms 33204 KB Output is correct
27 Correct 104 ms 32472 KB Output is correct
28 Correct 129 ms 34096 KB Output is correct
29 Correct 104 ms 33444 KB Output is correct
30 Correct 105 ms 34080 KB Output is correct
31 Correct 112 ms 32604 KB Output is correct

Subtask #5
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 8 ms 600 KB Output is correct
3 Correct 8 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 8 ms 604 KB Output is correct
6 Correct 8 ms 724 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 9 ms 804 KB Output is correct
10 Correct 11 ms 604 KB Output is correct
11 Correct 10 ms 604 KB Output is correct
12 Correct 10 ms 856 KB Output is correct
13 Correct 9 ms 604 KB Output is correct
14 Correct 10 ms 604 KB Output is correct
15 Correct 15 ms 604 KB Output is correct
16 Execution timed out 4040 ms 31132 KB Time limit exceeded
17 Halted 0 ms 0 KB -