oj.uz

답안 #981780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981780 2024-05-13T14:47:34 Z kaopj Evacuation plan (IZhO18_plan) C++14
100 / 100
 834 ms 84704 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(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(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:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |         auto [u , w] = pq.top();
      |              ^
plan.cpp:58:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         for(auto [v , ww] : adj[u]){
      |                  ^
plan.cpp: In function 'void dfs(int, int)':
plan.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for(auto [v , w] : tree[u]){
      |              ^
plan.cpp: In function 'int main()':
plan.cpp:138:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |     for(auto [u,v,w] : edge_input){
      |              ^
plan.cpp:144:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  144 |     for(auto [u,v,w] : edge_new){
      |              ^

Subtask #1
10.0 / 10.0

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

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 30040 KB Output is correct
2 Correct 9 ms 30300 KB Output is correct
3 Correct 10 ms 30300 KB Output is correct
4 Correct 6 ms 30044 KB Output is correct
5 Correct 8 ms 30244 KB Output is correct
6 Correct 8 ms 30296 KB Output is correct
7 Correct 6 ms 30296 KB Output is correct
8 Correct 6 ms 30064 KB Output is correct
9 Correct 8 ms 30300 KB Output is correct
10 Correct 8 ms 30336 KB Output is correct
11 Correct 8 ms 30300 KB Output is correct
12 Correct 11 ms 30300 KB Output is correct
13 Correct 8 ms 30300 KB Output is correct
14 Correct 8 ms 30256 KB Output is correct
15 Correct 8 ms 30328 KB Output is correct
16 Correct 314 ms 45628 KB Output is correct
17 Correct 745 ms 83756 KB Output is correct
18 Correct 58 ms 34868 KB Output is correct
19 Correct 324 ms 45908 KB Output is correct
20 Correct 737 ms 83916 KB Output is correct
21 Correct 462 ms 56224 KB Output is correct
22 Correct 320 ms 52648 KB Output is correct
23 Correct 752 ms 84056 KB Output is correct
24 Correct 834 ms 83880 KB Output is correct
25 Correct 807 ms 83772 KB Output is correct
26 Correct 302 ms 45848 KB Output is correct
27 Correct 317 ms 45972 KB Output is correct
28 Correct 291 ms 46344 KB Output is correct
29 Correct 303 ms 45896 KB Output is correct
30 Correct 302 ms 45952 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 30040 KB Output is correct
2 Correct 6 ms 30044 KB Output is correct
3 Correct 6 ms 30044 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 30044 KB Output is correct
9 Correct 6 ms 30288 KB Output is correct
10 Correct 6 ms 30300 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 254 ms 53228 KB Output is correct
2 Correct 560 ms 82316 KB Output is correct
3 Correct 578 ms 82240 KB Output is correct
4 Correct 134 ms 48248 KB Output is correct
5 Correct 541 ms 82120 KB Output is correct
6 Correct 547 ms 82076 KB Output is correct
7 Correct 549 ms 82136 KB Output is correct
8 Correct 563 ms 82112 KB Output is correct
9 Correct 557 ms 82884 KB Output is correct
10 Correct 538 ms 82212 KB Output is correct
11 Correct 542 ms 82440 KB Output is correct
12 Correct 544 ms 82316 KB Output is correct
13 Correct 611 ms 82224 KB Output is correct
14 Correct 538 ms 83044 KB Output is correct
15 Correct 547 ms 83112 KB Output is correct
16 Correct 530 ms 82080 KB Output is correct
17 Correct 555 ms 82144 KB Output is correct
18 Correct 557 ms 82796 KB Output is correct
19 Correct 134 ms 50236 KB Output is correct
20 Correct 546 ms 82432 KB Output is correct
21 Correct 528 ms 82764 KB Output is correct
22 Correct 118 ms 44308 KB Output is correct
23 Correct 127 ms 45548 KB Output is correct
24 Correct 133 ms 44464 KB Output is correct
25 Correct 129 ms 44244 KB Output is correct
26 Correct 139 ms 45888 KB Output is correct
27 Correct 150 ms 50100 KB Output is correct
28 Correct 125 ms 44404 KB Output is correct
29 Correct 157 ms 49188 KB Output is correct
30 Correct 118 ms 44456 KB Output is correct
31 Correct 151 ms 49208 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 30040 KB Output is correct
2 Correct 9 ms 30300 KB Output is correct
3 Correct 10 ms 30300 KB Output is correct
4 Correct 6 ms 30044 KB Output is correct
5 Correct 8 ms 30244 KB Output is correct
6 Correct 8 ms 30296 KB Output is correct
7 Correct 6 ms 30296 KB Output is correct
8 Correct 6 ms 30064 KB Output is correct
9 Correct 8 ms 30300 KB Output is correct
10 Correct 8 ms 30336 KB Output is correct
11 Correct 8 ms 30300 KB Output is correct
12 Correct 11 ms 30300 KB Output is correct
13 Correct 8 ms 30300 KB Output is correct
14 Correct 8 ms 30256 KB Output is correct
15 Correct 8 ms 30328 KB Output is correct
16 Correct 314 ms 45628 KB Output is correct
17 Correct 745 ms 83756 KB Output is correct
18 Correct 58 ms 34868 KB Output is correct
19 Correct 324 ms 45908 KB Output is correct
20 Correct 737 ms 83916 KB Output is correct
21 Correct 462 ms 56224 KB Output is correct
22 Correct 320 ms 52648 KB Output is correct
23 Correct 752 ms 84056 KB Output is correct
24 Correct 834 ms 83880 KB Output is correct
25 Correct 807 ms 83772 KB Output is correct
26 Correct 302 ms 45848 KB Output is correct
27 Correct 317 ms 45972 KB Output is correct
28 Correct 291 ms 46344 KB Output is correct
29 Correct 303 ms 45896 KB Output is correct
30 Correct 302 ms 45952 KB Output is correct
31 Correct 6 ms 30040 KB Output is correct
32 Correct 6 ms 30044 KB Output is correct
33 Correct 6 ms 30044 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 30044 KB Output is correct
39 Correct 6 ms 30288 KB Output is correct
40 Correct 6 ms 30300 KB Output is correct
41 Correct 254 ms 53228 KB Output is correct
42 Correct 560 ms 82316 KB Output is correct
43 Correct 578 ms 82240 KB Output is correct
44 Correct 134 ms 48248 KB Output is correct
45 Correct 541 ms 82120 KB Output is correct
46 Correct 547 ms 82076 KB Output is correct
47 Correct 549 ms 82136 KB Output is correct
48 Correct 563 ms 82112 KB Output is correct
49 Correct 557 ms 82884 KB Output is correct
50 Correct 538 ms 82212 KB Output is correct
51 Correct 542 ms 82440 KB Output is correct
52 Correct 544 ms 82316 KB Output is correct
53 Correct 611 ms 82224 KB Output is correct
54 Correct 538 ms 83044 KB Output is correct
55 Correct 547 ms 83112 KB Output is correct
56 Correct 530 ms 82080 KB Output is correct
57 Correct 555 ms 82144 KB Output is correct
58 Correct 557 ms 82796 KB Output is correct
59 Correct 134 ms 50236 KB Output is correct
60 Correct 546 ms 82432 KB Output is correct
61 Correct 528 ms 82764 KB Output is correct
62 Correct 118 ms 44308 KB Output is correct
63 Correct 127 ms 45548 KB Output is correct
64 Correct 133 ms 44464 KB Output is correct
65 Correct 129 ms 44244 KB Output is correct
66 Correct 139 ms 45888 KB Output is correct
67 Correct 150 ms 50100 KB Output is correct
68 Correct 125 ms 44404 KB Output is correct
69 Correct 157 ms 49188 KB Output is correct
70 Correct 118 ms 44456 KB Output is correct
71 Correct 151 ms 49208 KB Output is correct
72 Correct 463 ms 56140 KB Output is correct
73 Correct 754 ms 84008 KB Output is correct
74 Correct 738 ms 84460 KB Output is correct
75 Correct 753 ms 84028 KB Output is correct
76 Correct 713 ms 83788 KB Output is correct
77 Correct 742 ms 83972 KB Output is correct
78 Correct 718 ms 83748 KB Output is correct
79 Correct 753 ms 83924 KB Output is correct
80 Correct 761 ms 83796 KB Output is correct
81 Correct 726 ms 83708 KB Output is correct
82 Correct 732 ms 83840 KB Output is correct
83 Correct 751 ms 84584 KB Output is correct
84 Correct 761 ms 83924 KB Output is correct
85 Correct 741 ms 83964 KB Output is correct
86 Correct 712 ms 83948 KB Output is correct
87 Correct 770 ms 83784 KB Output is correct
88 Correct 733 ms 83972 KB Output is correct
89 Correct 383 ms 51416 KB Output is correct
90 Correct 722 ms 83860 KB Output is correct
91 Correct 734 ms 84704 KB Output is correct
92 Correct 310 ms 45836 KB Output is correct
93 Correct 336 ms 47928 KB Output is correct
94 Correct 310 ms 45900 KB Output is correct
95 Correct 313 ms 45848 KB Output is correct
96 Correct 330 ms 47672 KB Output is correct
97 Correct 381 ms 50036 KB Output is correct
98 Correct 305 ms 45860 KB Output is correct
99 Correct 396 ms 51824 KB Output is correct
100 Correct 314 ms 46436 KB Output is correct