oj.uz

답안 #157710

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
157710 2019-10-12T18:15:25 Z brcode Evacuation plan (IZhO18_plan) C++14
100 / 100
 1800 ms 56048 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1e5+5;
priority_queue<pair<int,int>> pq;
int par[MAXN];
int sz[MAXN];
int depth[MAXN];
int lift[MAXN][25];
int dp[MAXN];
int npp[MAXN];
vector<pair<int,int>> v1[MAXN];
vector<pair<int,int>> v2[MAXN];
vector<pair<int,pair<int,int>>> edges;
int lift2[MAXN][25];
int n,m;
int findpar(int a){
    if(par[a] == a){
        return a;
    }
    return par[a] = findpar(par[a]);
}
void merge(int a,int b){
    a = findpar(a);
    b = findpar(b);
    if(a == b){
        return;
    }
    if(sz[a]<sz[b]){
        swap(a,b);
    }
    par[b] = a;
    sz[a] += sz[b];
}
void dfs(int curr,int p,int lvl){

    depth[curr] = lvl;
    lift[curr][0] = p;

    for(auto x:v2[curr]){
        if(x.first!=p){
            lift2[x.first][0] = x.second;
            dfs(x.first,curr,lvl+1);
        }
    }
}
int lca(int a,int b){
    if(depth[a]<depth[b]){
        swap(a,b);
    }
    for(int i=20;i>=0;i--){
        if(lift[a][i]!=-1 && depth[lift[a][i]]>=depth[b]){
            a= lift[a][i];
        }
    }
    if(a==b){
        return a;
    }
    for(int i=20;i>=0;i--){
        if(lift[a][i]!=-1 && lift[a][i]!=lift[b][i]){
            a=lift[a][i];
            b = lift[b][i];
        }
    }
    return lift[a][0];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        dp[i] = 1e9;
        par[i] = i;
        sz[i] = 1;
    }
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        v1[x].push_back(make_pair(y,w));
        v1[y].push_back(make_pair(x,w));
    }
    int nppcount;
    cin>>nppcount;
    for(int i=1;i<=nppcount;i++){
        cin>>npp[i];
        pq.push(make_pair(0,npp[i]));
        dp[npp[i]] = 0;
    }
    while(!pq.empty()){
        auto hold = pq.top();
        int w = -1*hold.first;
        int curr = hold.second;
        pq.pop();
        for(auto x:v1[curr]){
            if(dp[curr]+x.second<dp[x.first]){
                dp[x.first] = dp[curr]+x.second;
                pq.push(make_pair(-dp[x.first],x.first));
            }
        }
    }
    //cout<<dp[9]<<endl;
    for(int i=1;i<=n;i++){
        for(int j=0;j<v1[i].size();j++){

            edges.push_back(make_pair(min(dp[v1[i][j].first],dp[i]),make_pair(i,v1[i][j].first)));
        }
    }
    sort(edges.begin(),edges.end());
    reverse(edges.begin(),edges.end());
    for(auto x:edges){
        int w = x.first;
        int a = x.second.first;
        int b = x.second.second;
        if(findpar(a)!=findpar(b)){
            merge(a,b);
            v2[a].push_back(make_pair(b,w));
            v2[b].push_back(make_pair(a,w));
            //cout<<a<<" "<<b<<" "<<w<<endl;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=20;j++){
            lift[i][j] = -1;
            lift2[i][j] = 1e9;
        }
    }
    dfs(1,-1,0);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            if(lift[i][j-1]==-1){
                lift[i][j] = -1;
            }else{
                lift[i][j] = lift[lift[i][j-1]][j-1];
            }

        }
    }
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            if(lift2[i][j-1]==1e9){
                lift2[i][j] = 1e9;
            }else{
                lift2[i][j] = min(lift2[lift[i][j-1]][j-1],lift2[i][j-1]);
            }

        }
    }
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        int c = lca(a,b);
       // cout<<c<<endl;
        int ans = 1e9;
        for(int j=20;j>=0;j--){
            if(lift[a][j]!=-1 && depth[lift[a][j]]>=depth[c]){
                ans = min(ans,lift2[a][j]);
                a =lift[a][j];
            }
        }
        for(int j=20;j>=0;j--){
            if(lift[b][j]!=-1 && depth[lift[b][j]]>=depth[c]){
                ans=min(ans,lift2[b][j]);
                b= lift[b][j];
            }
        }
        cout<<ans<<endl;
    }
}

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:91:13: warning: unused variable 'w' [-Wunused-variable]
         int w = -1*hold.first;
             ^
plan.cpp:103:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<v1[i].size();j++){
                     ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 12 ms 5368 KB Output is correct
3 Correct 11 ms 5368 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 12 ms 5368 KB Output is correct
6 Correct 12 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 11 ms 5368 KB Output is correct
10 Correct 12 ms 5368 KB Output is correct
11 Correct 12 ms 5496 KB Output is correct
12 Correct 12 ms 5368 KB Output is correct
13 Correct 12 ms 5368 KB Output is correct
14 Correct 12 ms 5444 KB Output is correct
15 Correct 12 ms 5412 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 12 ms 5368 KB Output is correct
3 Correct 11 ms 5368 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 12 ms 5368 KB Output is correct
6 Correct 12 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 11 ms 5368 KB Output is correct
10 Correct 12 ms 5368 KB Output is correct
11 Correct 12 ms 5496 KB Output is correct
12 Correct 12 ms 5368 KB Output is correct
13 Correct 12 ms 5368 KB Output is correct
14 Correct 12 ms 5444 KB Output is correct
15 Correct 12 ms 5412 KB Output is correct
16 Correct 751 ms 30696 KB Output is correct
17 Correct 1796 ms 55788 KB Output is correct
18 Correct 135 ms 10348 KB Output is correct
19 Correct 707 ms 37608 KB Output is correct
20 Correct 1778 ms 55820 KB Output is correct
21 Correct 1044 ms 41476 KB Output is correct
22 Correct 782 ms 40344 KB Output is correct
23 Correct 1758 ms 55640 KB Output is correct
24 Correct 1779 ms 55692 KB Output is correct
25 Correct 1778 ms 55624 KB Output is correct
26 Correct 702 ms 37348 KB Output is correct
27 Correct 697 ms 37444 KB Output is correct
28 Correct 710 ms 37456 KB Output is correct
29 Correct 694 ms 37540 KB Output is correct
30 Correct 700 ms 37572 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 585 ms 40664 KB Output is correct
2 Correct 1313 ms 55372 KB Output is correct
3 Correct 1301 ms 55428 KB Output is correct
4 Correct 311 ms 37672 KB Output is correct
5 Correct 1288 ms 55196 KB Output is correct
6 Correct 1291 ms 55368 KB Output is correct
7 Correct 1302 ms 55224 KB Output is correct
8 Correct 1305 ms 55236 KB Output is correct
9 Correct 1331 ms 55188 KB Output is correct
10 Correct 1293 ms 55260 KB Output is correct
11 Correct 1343 ms 55284 KB Output is correct
12 Correct 1311 ms 55236 KB Output is correct
13 Correct 1301 ms 55196 KB Output is correct
14 Correct 1297 ms 55280 KB Output is correct
15 Correct 1304 ms 55288 KB Output is correct
16 Correct 1317 ms 55304 KB Output is correct
17 Correct 1315 ms 55396 KB Output is correct
18 Correct 1316 ms 55292 KB Output is correct
19 Correct 311 ms 39268 KB Output is correct
20 Correct 1322 ms 55256 KB Output is correct
21 Correct 1235 ms 55436 KB Output is correct
22 Correct 295 ms 37092 KB Output is correct
23 Correct 315 ms 36204 KB Output is correct
24 Correct 283 ms 37208 KB Output is correct
25 Correct 277 ms 37092 KB Output is correct
26 Correct 328 ms 36580 KB Output is correct
27 Correct 336 ms 39020 KB Output is correct
28 Correct 296 ms 37080 KB Output is correct
29 Correct 317 ms 38296 KB Output is correct
30 Correct 287 ms 37208 KB Output is correct
31 Correct 312 ms 38448 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 12 ms 5368 KB Output is correct
3 Correct 11 ms 5368 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 12 ms 5368 KB Output is correct
6 Correct 12 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 11 ms 5368 KB Output is correct
10 Correct 12 ms 5368 KB Output is correct
11 Correct 12 ms 5496 KB Output is correct
12 Correct 12 ms 5368 KB Output is correct
13 Correct 12 ms 5368 KB Output is correct
14 Correct 12 ms 5444 KB Output is correct
15 Correct 12 ms 5412 KB Output is correct
16 Correct 751 ms 30696 KB Output is correct
17 Correct 1796 ms 55788 KB Output is correct
18 Correct 135 ms 10348 KB Output is correct
19 Correct 707 ms 37608 KB Output is correct
20 Correct 1778 ms 55820 KB Output is correct
21 Correct 1044 ms 41476 KB Output is correct
22 Correct 782 ms 40344 KB Output is correct
23 Correct 1758 ms 55640 KB Output is correct
24 Correct 1779 ms 55692 KB Output is correct
25 Correct 1778 ms 55624 KB Output is correct
26 Correct 702 ms 37348 KB Output is correct
27 Correct 697 ms 37444 KB Output is correct
28 Correct 710 ms 37456 KB Output is correct
29 Correct 694 ms 37540 KB Output is correct
30 Correct 700 ms 37572 KB Output is correct
31 Correct 6 ms 4984 KB Output is correct
32 Correct 7 ms 5112 KB Output is correct
33 Correct 7 ms 5112 KB Output is correct
34 Correct 6 ms 4984 KB Output is correct
35 Correct 6 ms 5112 KB Output is correct
36 Correct 6 ms 5112 KB Output is correct
37 Correct 6 ms 5112 KB Output is correct
38 Correct 6 ms 4984 KB Output is correct
39 Correct 6 ms 5112 KB Output is correct
40 Correct 6 ms 5112 KB Output is correct
41 Correct 585 ms 40664 KB Output is correct
42 Correct 1313 ms 55372 KB Output is correct
43 Correct 1301 ms 55428 KB Output is correct
44 Correct 311 ms 37672 KB Output is correct
45 Correct 1288 ms 55196 KB Output is correct
46 Correct 1291 ms 55368 KB Output is correct
47 Correct 1302 ms 55224 KB Output is correct
48 Correct 1305 ms 55236 KB Output is correct
49 Correct 1331 ms 55188 KB Output is correct
50 Correct 1293 ms 55260 KB Output is correct
51 Correct 1343 ms 55284 KB Output is correct
52 Correct 1311 ms 55236 KB Output is correct
53 Correct 1301 ms 55196 KB Output is correct
54 Correct 1297 ms 55280 KB Output is correct
55 Correct 1304 ms 55288 KB Output is correct
56 Correct 1317 ms 55304 KB Output is correct
57 Correct 1315 ms 55396 KB Output is correct
58 Correct 1316 ms 55292 KB Output is correct
59 Correct 311 ms 39268 KB Output is correct
60 Correct 1322 ms 55256 KB Output is correct
61 Correct 1235 ms 55436 KB Output is correct
62 Correct 295 ms 37092 KB Output is correct
63 Correct 315 ms 36204 KB Output is correct
64 Correct 283 ms 37208 KB Output is correct
65 Correct 277 ms 37092 KB Output is correct
66 Correct 328 ms 36580 KB Output is correct
67 Correct 336 ms 39020 KB Output is correct
68 Correct 296 ms 37080 KB Output is correct
69 Correct 317 ms 38296 KB Output is correct
70 Correct 287 ms 37208 KB Output is correct
71 Correct 312 ms 38448 KB Output is correct
72 Correct 1056 ms 41324 KB Output is correct
73 Correct 1764 ms 55560 KB Output is correct
74 Correct 1766 ms 55796 KB Output is correct
75 Correct 1771 ms 55588 KB Output is correct
76 Correct 1754 ms 55752 KB Output is correct
77 Correct 1774 ms 55604 KB Output is correct
78 Correct 1765 ms 55560 KB Output is correct
79 Correct 1757 ms 55648 KB Output is correct
80 Correct 1800 ms 55692 KB Output is correct
81 Correct 1754 ms 55704 KB Output is correct
82 Correct 1761 ms 55696 KB Output is correct
83 Correct 1758 ms 55612 KB Output is correct
84 Correct 1768 ms 55660 KB Output is correct
85 Correct 1754 ms 55796 KB Output is correct
86 Correct 1765 ms 55688 KB Output is correct
87 Correct 1757 ms 55636 KB Output is correct
88 Correct 1767 ms 55620 KB Output is correct
89 Correct 871 ms 39432 KB Output is correct
90 Correct 1752 ms 55664 KB Output is correct
91 Correct 1709 ms 56048 KB Output is correct
92 Correct 716 ms 37700 KB Output is correct
93 Correct 863 ms 37452 KB Output is correct
94 Correct 734 ms 37736 KB Output is correct
95 Correct 711 ms 37772 KB Output is correct
96 Correct 841 ms 37252 KB Output is correct
97 Correct 934 ms 38656 KB Output is correct
98 Correct 731 ms 37512 KB Output is correct
99 Correct 1012 ms 39744 KB Output is correct
100 Correct 725 ms 37864 KB Output is correct