oj.uz

답안 #979604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
979604 2024-05-11T08:13:27 Z SeenSiravit Evacuation plan (IZhO18_plan) C++14
100 / 100
 821 ms 84948 KB 
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define pill pair<int,ll>

using namespace std;

const int mxN = 1e5 + 5 , mxLogDepth = 20 , limDepth=17;

struct EDGE {
    int u,v;
    ll w;

    bool operator < (const EDGE &d2) const{
        return w > d2.w;
    }
};

struct ADJ {
    int u;
    ll w;

    bool operator < (const ADJ &d2) const{
        return w > d2.w;
    }
};


int n,m,n_npp;
vector<ADJ> adj[mxN];
vector<EDGE> edge_input;
vector<EDGE> edge_new;
vector<ADJ> tree[mxN];
bool npp[mxN];
ll dis[mxN];
int cmp[mxN];
int depth[mxN];
ll dp[mxN][mxLogDepth];
int ancestor[mxN][mxLogDepth];

void dijkstra_npp(){
    for(int i=1;i<=n;i++) dis[i] = LLONG_MAX;

    priority_queue<ADJ> pq;

    for(int i=1;i<=n;i++){
        if(npp[i]){
            dis[i] = 0;
            pq.push({i , dis[i]});
        }
    }

    while(!pq.empty()){
        auto [u , w] = pq.top();
        pq.pop();

        if(dis[u] < w) continue;

        for(auto [v , ww] : adj[u]){
            if(dis[v] > w + ww){
                dis[v] = w + ww;
                pq.push({v , dis[v]});
            }
        }
    }
}

int fp(int x){
    if(cmp[x] == x) return x;
    return cmp[x] = fp(cmp[x]);
}

void dfs(int u , int pa){
    for(auto [v , w] : tree[u]){
        if(v == pa) continue;

        depth[v] = depth[u] + 1;
        ancestor[v][0] = u;
        dp[v][0] = w;
        
        dfs(v , u);
    }
}

void lca(int u, int v){
    if(depth[u] > depth[v]) swap(u , v);

    int diff = depth[v]- depth[u];
    ll ans = min(dis[u] , dis[v]);

    for(int k=0;k<=limDepth;k++){
        if((1<<k) & diff){
            ans = min(ans , dp[v][k]);
            v = ancestor[v][k];
        }
    }

    if(u == v){
        cout<< ans << '\n';
        return ;
    }

    for(int k=limDepth;k>=0;k--){
        if(ancestor[u][k] != ancestor[v][k]){
            ans = min({ans , dp[u][k] , dp[v][k]});
            u = ancestor[u][k];
            v = ancestor[v][k];
        }
    }

    ans = min({ans , dp[u][0] , dp[v][0]});
    cout<< ans << '\n';
}

int main(){
    cin>> n >> m;

    for(int i=0;i<m;i++){
        int u,v;
        ll w;
        cin>> u >> v >> w;
        
        adj[u].push_back({v , w});
        adj[v].push_back({u , w});

        edge_input.push_back({u , v , w});
    }

    int n_npp;
    cin>> n_npp;

    for(int i=1;i<=n;i++) npp[i] = false;
    for(int i=0;i<n_npp;i++){
        int node;
        cin>> node;
        npp[node] = true;
    }

    dijkstra_npp();
    // for(int i=1;i<=n;i++) cout<< dis[i] <<  " ";
    // cout<< "\n";

    for(auto [u,v,w] : edge_input){
        edge_new.push_back({u , v , min(dis[u] , dis[v])});
    }

    sort(edge_new.begin() , edge_new.end());

    // for(auto [u,v,w] : edge_new) cout<< u << " " << v << " " << w << "\n";

    for(int i=1;i<=n;i++) cmp[i] = i;

    for(auto [u,v,w] : edge_new){
        int pa_u = fp(u) , pa_v = fp(v);

        if(pa_u == pa_v) continue;

        tree[u].push_back({v , w});
        tree[v].push_back({u , w});
        cmp[pa_v] = pa_u;
    }

    for(int i=0;i<mxN;i++){
        for(int j=0;j<mxLogDepth;j++){
            dp[i][j] = LLONG_MAX;
            ancestor[i][j] = 0;
        }
    }

    dfs(1 , -1);

    for(int k=1;k<=limDepth;k++){
        for(int node=1;node<=n;node++){
            ancestor[node][k] = ancestor[ancestor[node][k-1]][k-1];
            dp[node][k] = min(dp[node][k-1] , dp[ancestor[node][k-1]][k-1]);
        }
    }

    int q;
    cin>> q;

    while(q--){
        int u,v;
        cin>> u >> v;
        lca(u , v);
    }
}

Compilation message

plan.cpp: In function 'void dijkstra_npp()':
plan.cpp:54:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |         auto [u , w] = pq.top();
      |              ^
plan.cpp:59:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for(auto [v , ww] : adj[u]){
      |                  ^
plan.cpp: In function 'void dfs(int, int)':
plan.cpp:74:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |     for(auto [v , w] : tree[u]){
      |              ^
plan.cpp: In function 'int main()':
plan.cpp:143:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  143 |     for(auto [u,v,w] : edge_input){
      |              ^
plan.cpp:153:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |     for(auto [u,v,w] : edge_new){
      |              ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 30044 KB Output is correct
2 Correct 8 ms 30300 KB Output is correct
3 Correct 8 ms 30300 KB Output is correct
4 Correct 6 ms 30064 KB Output is correct
5 Correct 8 ms 30404 KB Output is correct
6 Correct 8 ms 30300 KB Output is correct
7 Correct 6 ms 30300 KB Output is correct
8 Correct 6 ms 30060 KB Output is correct
9 Correct 8 ms 30296 KB Output is correct
10 Correct 8 ms 30300 KB Output is correct
11 Correct 8 ms 30300 KB Output is correct
12 Correct 8 ms 30300 KB Output is correct
13 Correct 8 ms 30300 KB Output is correct
14 Correct 10 ms 30440 KB Output is correct
15 Correct 8 ms 30300 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 30044 KB Output is correct
2 Correct 8 ms 30300 KB Output is correct
3 Correct 8 ms 30300 KB Output is correct
4 Correct 6 ms 30064 KB Output is correct
5 Correct 8 ms 30404 KB Output is correct
6 Correct 8 ms 30300 KB Output is correct
7 Correct 6 ms 30300 KB Output is correct
8 Correct 6 ms 30060 KB Output is correct
9 Correct 8 ms 30296 KB Output is correct
10 Correct 8 ms 30300 KB Output is correct
11 Correct 8 ms 30300 KB Output is correct
12 Correct 8 ms 30300 KB Output is correct
13 Correct 8 ms 30300 KB Output is correct
14 Correct 10 ms 30440 KB Output is correct
15 Correct 8 ms 30300 KB Output is correct
16 Correct 306 ms 45592 KB Output is correct
17 Correct 728 ms 84236 KB Output is correct
18 Correct 61 ms 34876 KB Output is correct
19 Correct 293 ms 45956 KB Output is correct
20 Correct 725 ms 83892 KB Output is correct
21 Correct 429 ms 57140 KB Output is correct
22 Correct 305 ms 52536 KB Output is correct
23 Correct 714 ms 83832 KB Output is correct
24 Correct 714 ms 84948 KB Output is correct
25 Correct 711 ms 84052 KB Output is correct
26 Correct 294 ms 45780 KB Output is correct
27 Correct 299 ms 46308 KB Output is correct
28 Correct 289 ms 45840 KB Output is correct
29 Correct 295 ms 46032 KB Output is correct
30 Correct 289 ms 46084 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 30044 KB Output is correct
2 Correct 6 ms 30068 KB Output is correct
3 Correct 6 ms 30040 KB Output is correct
4 Correct 6 ms 30300 KB Output is correct
5 Correct 6 ms 30300 KB Output is correct
6 Correct 6 ms 30300 KB Output is correct
7 Correct 6 ms 30300 KB Output is correct
8 Correct 6 ms 30288 KB Output is correct
9 Correct 6 ms 30040 KB Output is correct
10 Correct 6 ms 30044 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 51024 KB Output is correct
2 Correct 512 ms 82244 KB Output is correct
3 Correct 528 ms 82492 KB Output is correct
4 Correct 140 ms 48276 KB Output is correct
5 Correct 528 ms 82656 KB Output is correct
6 Correct 534 ms 82212 KB Output is correct
7 Correct 518 ms 82136 KB Output is correct
8 Correct 556 ms 82760 KB Output is correct
9 Correct 527 ms 82100 KB Output is correct
10 Correct 516 ms 82196 KB Output is correct
11 Correct 594 ms 82308 KB Output is correct
12 Correct 541 ms 82216 KB Output is correct
13 Correct 524 ms 82216 KB Output is correct
14 Correct 535 ms 82680 KB Output is correct
15 Correct 538 ms 82392 KB Output is correct
16 Correct 532 ms 82132 KB Output is correct
17 Correct 590 ms 82980 KB Output is correct
18 Correct 535 ms 82456 KB Output is correct
19 Correct 140 ms 50856 KB Output is correct
20 Correct 516 ms 82196 KB Output is correct
21 Correct 518 ms 82520 KB Output is correct
22 Correct 128 ms 44356 KB Output is correct
23 Correct 154 ms 45588 KB Output is correct
24 Correct 117 ms 44272 KB Output is correct
25 Correct 117 ms 44312 KB Output is correct
26 Correct 138 ms 45888 KB Output is correct
27 Correct 137 ms 49980 KB Output is correct
28 Correct 118 ms 44324 KB Output is correct
29 Correct 137 ms 48956 KB Output is correct
30 Correct 117 ms 44816 KB Output is correct
31 Correct 138 ms 49204 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 30044 KB Output is correct
2 Correct 8 ms 30300 KB Output is correct
3 Correct 8 ms 30300 KB Output is correct
4 Correct 6 ms 30064 KB Output is correct
5 Correct 8 ms 30404 KB Output is correct
6 Correct 8 ms 30300 KB Output is correct
7 Correct 6 ms 30300 KB Output is correct
8 Correct 6 ms 30060 KB Output is correct
9 Correct 8 ms 30296 KB Output is correct
10 Correct 8 ms 30300 KB Output is correct
11 Correct 8 ms 30300 KB Output is correct
12 Correct 8 ms 30300 KB Output is correct
13 Correct 8 ms 30300 KB Output is correct
14 Correct 10 ms 30440 KB Output is correct
15 Correct 8 ms 30300 KB Output is correct
16 Correct 306 ms 45592 KB Output is correct
17 Correct 728 ms 84236 KB Output is correct
18 Correct 61 ms 34876 KB Output is correct
19 Correct 293 ms 45956 KB Output is correct
20 Correct 725 ms 83892 KB Output is correct
21 Correct 429 ms 57140 KB Output is correct
22 Correct 305 ms 52536 KB Output is correct
23 Correct 714 ms 83832 KB Output is correct
24 Correct 714 ms 84948 KB Output is correct
25 Correct 711 ms 84052 KB Output is correct
26 Correct 294 ms 45780 KB Output is correct
27 Correct 299 ms 46308 KB Output is correct
28 Correct 289 ms 45840 KB Output is correct
29 Correct 295 ms 46032 KB Output is correct
30 Correct 289 ms 46084 KB Output is correct
31 Correct 5 ms 30044 KB Output is correct
32 Correct 6 ms 30068 KB Output is correct
33 Correct 6 ms 30040 KB Output is correct
34 Correct 6 ms 30300 KB Output is correct
35 Correct 6 ms 30300 KB Output is correct
36 Correct 6 ms 30300 KB Output is correct
37 Correct 6 ms 30300 KB Output is correct
38 Correct 6 ms 30288 KB Output is correct
39 Correct 6 ms 30040 KB Output is correct
40 Correct 6 ms 30044 KB Output is correct
41 Correct 237 ms 51024 KB Output is correct
42 Correct 512 ms 82244 KB Output is correct
43 Correct 528 ms 82492 KB Output is correct
44 Correct 140 ms 48276 KB Output is correct
45 Correct 528 ms 82656 KB Output is correct
46 Correct 534 ms 82212 KB Output is correct
47 Correct 518 ms 82136 KB Output is correct
48 Correct 556 ms 82760 KB Output is correct
49 Correct 527 ms 82100 KB Output is correct
50 Correct 516 ms 82196 KB Output is correct
51 Correct 594 ms 82308 KB Output is correct
52 Correct 541 ms 82216 KB Output is correct
53 Correct 524 ms 82216 KB Output is correct
54 Correct 535 ms 82680 KB Output is correct
55 Correct 538 ms 82392 KB Output is correct
56 Correct 532 ms 82132 KB Output is correct
57 Correct 590 ms 82980 KB Output is correct
58 Correct 535 ms 82456 KB Output is correct
59 Correct 140 ms 50856 KB Output is correct
60 Correct 516 ms 82196 KB Output is correct
61 Correct 518 ms 82520 KB Output is correct
62 Correct 128 ms 44356 KB Output is correct
63 Correct 154 ms 45588 KB Output is correct
64 Correct 117 ms 44272 KB Output is correct
65 Correct 117 ms 44312 KB Output is correct
66 Correct 138 ms 45888 KB Output is correct
67 Correct 137 ms 49980 KB Output is correct
68 Correct 118 ms 44324 KB Output is correct
69 Correct 137 ms 48956 KB Output is correct
70 Correct 117 ms 44816 KB Output is correct
71 Correct 138 ms 49204 KB Output is correct
72 Correct 462 ms 58080 KB Output is correct
73 Correct 698 ms 83940 KB Output is correct
74 Correct 709 ms 84372 KB Output is correct
75 Correct 728 ms 84032 KB Output is correct
76 Correct 722 ms 83888 KB Output is correct
77 Correct 728 ms 83924 KB Output is correct
78 Correct 723 ms 84004 KB Output is correct
79 Correct 748 ms 83940 KB Output is correct
80 Correct 750 ms 84088 KB Output is correct
81 Correct 728 ms 83780 KB Output is correct
82 Correct 704 ms 83744 KB Output is correct
83 Correct 745 ms 83944 KB Output is correct
84 Correct 756 ms 84492 KB Output is correct
85 Correct 792 ms 84004 KB Output is correct
86 Correct 766 ms 83784 KB Output is correct
87 Correct 737 ms 83744 KB Output is correct
88 Correct 821 ms 83820 KB Output is correct
89 Correct 418 ms 51200 KB Output is correct
90 Correct 728 ms 84180 KB Output is correct
91 Correct 779 ms 84172 KB Output is correct
92 Correct 295 ms 45832 KB Output is correct
93 Correct 418 ms 47808 KB Output is correct
94 Correct 311 ms 45892 KB Output is correct
95 Correct 303 ms 45840 KB Output is correct
96 Correct 379 ms 47788 KB Output is correct
97 Correct 359 ms 50332 KB Output is correct
98 Correct 336 ms 45724 KB Output is correct
99 Correct 345 ms 51808 KB Output is correct
100 Correct 320 ms 45908 KB Output is correct