oj.uz

Submission #468156

# Submission time Handle Problem Language Result Execution time Memory
468156 2021-08-26T23:16:25 Z nickmet2004 Evacuation plan (IZhO18_plan) C++11
100 / 100
 758 ms 100404 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int , int> ipair;
const int N = 5e5 + 5;
int n , m;
vector<pair<int , int> > adj[N];
int d[N] , vis[N];
int par[N] , sz[N];
int P[N][20] , mn[N][20] , depth[N];
struct Node{
    int u , v , w;
}E[N];
bool cmp(Node& X , Node& Y){
    return X.w < Y.w;
}
int Find(int x){
    if(par[x] == -1) return x;
    return par[x] = Find(par[x]);
}
int Un(int u , int v){
    u = Find(u);
    v = Find(v);
    if(u==v)return 0;
    if(sz[u] < sz[v])swap(u , v);
    par[v] = u;
    sz[u] += sz[v];
    return 1;
}
void dfs(int u , int p , int W){
    P[u][0] = p;
    mn[u][0] = W;
    for(int i = 1; i <= 17; ++i) P[u][i] = P[P[u][i - 1]][i - 1] , mn[u][i] = min(mn[u][i - 1] , mn[P[u][i - 1]][i - 1]);
    for(auto E : adj[u]){
        if(E.first==p)continue;
        depth[E.first] = depth[u] + 1;
        dfs(E.first , u , E.second);
    }
}
int LCA(int u , int v){
    if(depth[u] < depth[v])swap(u , v);
    int k = depth[u] - depth[v];
    int res = 1e18;
    for(int i = 18; ~i; --i){
        if(k>>i&1) res = min(res , mn[u][i]) , u = P[u][i];
    }
    if(u == v) return res;
    for(int i = 17; ~i; --i){
        if(P[u][i] != P[v][i]){
            res = min({res , mn[u][i] , mn[v][i]});
            u = P[u][i];
            v = P[v][i];
        }
    }
    return min({res , mn[u][0] , mn[v][0]});
}
 main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    int u , v ,w;
    for(int i = 0; i < m; ++i){
        cin >> u >> v >> w;
        adj[u].emplace_back(v , w);
        adj[v].emplace_back(u , w);
        E[i].u = u , E[i].v = v , E[i].w = w;
    }
    priority_queue<pair<int,  int>> pq;
    for(int i =1; i <= n; ++i) d[i] = 1e18;
    int k;
    cin >> k;
    int a;
    for(int i = 0;i < k; ++i){
        cin >> a;
        d[a] = 0;
        pq.push({0 ,a});
    }
    while(pq.size()){
        int u = pq.top().second;
        pq.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(auto E : adj[u]){
            int v = E.first , w = E.second;
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                pq.push({-d[v] , v});
            }
        }
    }

    for(int i = 0; i < m; ++i) E[i].w = -min(d[E[i].u] , d[E[i].v]);
    sort(E , E + m ,cmp);
    memset(par ,-1 , sizeof(par));
    for(int i = 1; i <= n; ++i) adj[i].clear() , sz[i] =1;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= 20; ++j) mn[i][j] = 1e18;
    }
    for(int i = 0; i < m; ++i){
        int ux = E[i].u , vx = E[i].v , wx = -E[i].w;
        if(Un(ux , vx)){
            adj[ux].emplace_back(vx , wx);
            adj[vx].emplace_back(ux , wx);
        }
    }
    mn[1][0] = 1e18;
    dfs(1 , 0 ,1e18);
    int q;
    cin >> q;
    while(q--){
        int A , B;
        cin >> A >> B;
        cout << LCA(A , B) << endl;
    }

}

Compilation message

plan.cpp:57:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 |  main (){
      |  ^~~~
plan.cpp: In function 'int main()':
plan.cpp:96:47: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   96 |         for(int j = 1; j <= 20; ++j) mn[i][j] = 1e18;
      |                                      ~~~~~~~~~^~~~~~
plan.cpp:96:26: note: within this loop
   96 |         for(int j = 1; j <= 20; ++j) mn[i][j] = 1e18;
      |                        ~~^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 11 ms 16460 KB Output is correct
3 Correct 12 ms 16472 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 12 ms 16460 KB Output is correct
6 Correct 12 ms 16428 KB Output is correct
7 Correct 9 ms 16076 KB Output is correct
8 Correct 9 ms 16032 KB Output is correct
9 Correct 12 ms 16460 KB Output is correct
10 Correct 12 ms 16424 KB Output is correct
11 Correct 12 ms 16460 KB Output is correct
12 Correct 12 ms 16376 KB Output is correct
13 Correct 13 ms 16460 KB Output is correct
14 Correct 12 ms 16428 KB Output is correct
15 Correct 12 ms 16460 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 11 ms 16460 KB Output is correct
3 Correct 12 ms 16472 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 12 ms 16460 KB Output is correct
6 Correct 12 ms 16428 KB Output is correct
7 Correct 9 ms 16076 KB Output is correct
8 Correct 9 ms 16032 KB Output is correct
9 Correct 12 ms 16460 KB Output is correct
10 Correct 12 ms 16424 KB Output is correct
11 Correct 12 ms 16460 KB Output is correct
12 Correct 12 ms 16376 KB Output is correct
13 Correct 13 ms 16460 KB Output is correct
14 Correct 12 ms 16428 KB Output is correct
15 Correct 12 ms 16460 KB Output is correct
16 Correct 350 ms 54244 KB Output is correct
17 Correct 740 ms 100404 KB Output is correct
18 Correct 60 ms 24500 KB Output is correct
19 Correct 331 ms 62536 KB Output is correct
20 Correct 717 ms 100220 KB Output is correct
21 Correct 468 ms 72116 KB Output is correct
22 Correct 353 ms 65868 KB Output is correct
23 Correct 723 ms 100264 KB Output is correct
24 Correct 718 ms 100148 KB Output is correct
25 Correct 711 ms 100168 KB Output is correct
26 Correct 325 ms 62260 KB Output is correct
27 Correct 322 ms 62388 KB Output is correct
28 Correct 325 ms 62400 KB Output is correct
29 Correct 320 ms 62356 KB Output is correct
30 Correct 327 ms 62456 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 9 ms 15948 KB Output is correct
3 Correct 9 ms 16032 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 9 ms 15948 KB Output is correct
6 Correct 9 ms 16020 KB Output is correct
7 Correct 10 ms 15948 KB Output is correct
8 Correct 10 ms 15948 KB Output is correct
9 Correct 10 ms 15948 KB Output is correct
10 Correct 10 ms 15948 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 67068 KB Output is correct
2 Correct 490 ms 90240 KB Output is correct
3 Correct 498 ms 90440 KB Output is correct
4 Correct 153 ms 60356 KB Output is correct
5 Correct 497 ms 90316 KB Output is correct
6 Correct 486 ms 90288 KB Output is correct
7 Correct 503 ms 90460 KB Output is correct
8 Correct 490 ms 90292 KB Output is correct
9 Correct 487 ms 90296 KB Output is correct
10 Correct 494 ms 90336 KB Output is correct
11 Correct 487 ms 90292 KB Output is correct
12 Correct 495 ms 90384 KB Output is correct
13 Correct 490 ms 90288 KB Output is correct
14 Correct 482 ms 90360 KB Output is correct
15 Correct 487 ms 90372 KB Output is correct
16 Correct 490 ms 90296 KB Output is correct
17 Correct 495 ms 90332 KB Output is correct
18 Correct 491 ms 90484 KB Output is correct
19 Correct 147 ms 61888 KB Output is correct
20 Correct 493 ms 98452 KB Output is correct
21 Correct 453 ms 98312 KB Output is correct
22 Correct 128 ms 60848 KB Output is correct
23 Correct 148 ms 60056 KB Output is correct
24 Correct 134 ms 60836 KB Output is correct
25 Correct 131 ms 60768 KB Output is correct
26 Correct 154 ms 60308 KB Output is correct
27 Correct 167 ms 63432 KB Output is correct
28 Correct 132 ms 60728 KB Output is correct
29 Correct 157 ms 62588 KB Output is correct
30 Correct 133 ms 60824 KB Output is correct
31 Correct 162 ms 62736 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15948 KB Output is correct
2 Correct 11 ms 16460 KB Output is correct
3 Correct 12 ms 16472 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 12 ms 16460 KB Output is correct
6 Correct 12 ms 16428 KB Output is correct
7 Correct 9 ms 16076 KB Output is correct
8 Correct 9 ms 16032 KB Output is correct
9 Correct 12 ms 16460 KB Output is correct
10 Correct 12 ms 16424 KB Output is correct
11 Correct 12 ms 16460 KB Output is correct
12 Correct 12 ms 16376 KB Output is correct
13 Correct 13 ms 16460 KB Output is correct
14 Correct 12 ms 16428 KB Output is correct
15 Correct 12 ms 16460 KB Output is correct
16 Correct 350 ms 54244 KB Output is correct
17 Correct 740 ms 100404 KB Output is correct
18 Correct 60 ms 24500 KB Output is correct
19 Correct 331 ms 62536 KB Output is correct
20 Correct 717 ms 100220 KB Output is correct
21 Correct 468 ms 72116 KB Output is correct
22 Correct 353 ms 65868 KB Output is correct
23 Correct 723 ms 100264 KB Output is correct
24 Correct 718 ms 100148 KB Output is correct
25 Correct 711 ms 100168 KB Output is correct
26 Correct 325 ms 62260 KB Output is correct
27 Correct 322 ms 62388 KB Output is correct
28 Correct 325 ms 62400 KB Output is correct
29 Correct 320 ms 62356 KB Output is correct
30 Correct 327 ms 62456 KB Output is correct
31 Correct 9 ms 15948 KB Output is correct
32 Correct 9 ms 15948 KB Output is correct
33 Correct 9 ms 16032 KB Output is correct
34 Correct 9 ms 15948 KB Output is correct
35 Correct 9 ms 15948 KB Output is correct
36 Correct 9 ms 16020 KB Output is correct
37 Correct 10 ms 15948 KB Output is correct
38 Correct 10 ms 15948 KB Output is correct
39 Correct 10 ms 15948 KB Output is correct
40 Correct 10 ms 15948 KB Output is correct
41 Correct 270 ms 67068 KB Output is correct
42 Correct 490 ms 90240 KB Output is correct
43 Correct 498 ms 90440 KB Output is correct
44 Correct 153 ms 60356 KB Output is correct
45 Correct 497 ms 90316 KB Output is correct
46 Correct 486 ms 90288 KB Output is correct
47 Correct 503 ms 90460 KB Output is correct
48 Correct 490 ms 90292 KB Output is correct
49 Correct 487 ms 90296 KB Output is correct
50 Correct 494 ms 90336 KB Output is correct
51 Correct 487 ms 90292 KB Output is correct
52 Correct 495 ms 90384 KB Output is correct
53 Correct 490 ms 90288 KB Output is correct
54 Correct 482 ms 90360 KB Output is correct
55 Correct 487 ms 90372 KB Output is correct
56 Correct 490 ms 90296 KB Output is correct
57 Correct 495 ms 90332 KB Output is correct
58 Correct 491 ms 90484 KB Output is correct
59 Correct 147 ms 61888 KB Output is correct
60 Correct 493 ms 98452 KB Output is correct
61 Correct 453 ms 98312 KB Output is correct
62 Correct 128 ms 60848 KB Output is correct
63 Correct 148 ms 60056 KB Output is correct
64 Correct 134 ms 60836 KB Output is correct
65 Correct 131 ms 60768 KB Output is correct
66 Correct 154 ms 60308 KB Output is correct
67 Correct 167 ms 63432 KB Output is correct
68 Correct 132 ms 60728 KB Output is correct
69 Correct 157 ms 62588 KB Output is correct
70 Correct 133 ms 60824 KB Output is correct
71 Correct 162 ms 62736 KB Output is correct
72 Correct 497 ms 72092 KB Output is correct
73 Correct 740 ms 100004 KB Output is correct
74 Correct 736 ms 100248 KB Output is correct
75 Correct 726 ms 100148 KB Output is correct
76 Correct 717 ms 100148 KB Output is correct
77 Correct 730 ms 100188 KB Output is correct
78 Correct 727 ms 100064 KB Output is correct
79 Correct 718 ms 100024 KB Output is correct
80 Correct 723 ms 100084 KB Output is correct
81 Correct 727 ms 100044 KB Output is correct
82 Correct 739 ms 100100 KB Output is correct
83 Correct 726 ms 100144 KB Output is correct
84 Correct 727 ms 100216 KB Output is correct
85 Correct 737 ms 100196 KB Output is correct
86 Correct 730 ms 100152 KB Output is correct
87 Correct 758 ms 100076 KB Output is correct
88 Correct 743 ms 100076 KB Output is correct
89 Correct 444 ms 64964 KB Output is correct
90 Correct 726 ms 100280 KB Output is correct
91 Correct 715 ms 99756 KB Output is correct
92 Correct 361 ms 62416 KB Output is correct
93 Correct 405 ms 62116 KB Output is correct
94 Correct 353 ms 62280 KB Output is correct
95 Correct 361 ms 62280 KB Output is correct
96 Correct 420 ms 62148 KB Output is correct
97 Correct 455 ms 63884 KB Output is correct
98 Correct 343 ms 62172 KB Output is correct
99 Correct 451 ms 65148 KB Output is correct
100 Correct 352 ms 62304 KB Output is correct