oj.uz

Submission #367207

# Submission time Handle Problem Language Result Execution time Memory
367207 2021-02-16T14:48:37 Z nicolaalexandra Evacuation plan (IZhO18_plan) C++14
100 / 100
 1357 ms 89280 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;

struct muchie{
    int x,y,cost;
};
vector <muchie> mch;

vector <pair<int,int> > L[DIM],edg[DIM];
priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > h;
int E[DIM*4],p[DIM*4],level[DIM],t[DIM],first[DIM],dist[DIM],v[DIM];
pair <int,int> rmq[21][DIM*4],dp[21][DIM];
int n,m,q,x,y,cost,i,j,k,cnt;

inline int cmp (muchie a, muchie b){
    return a.cost > b.cost;
}

int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}

void dfs (int nod, int tata){
    E[++k] = nod;
    first[nod] = k;
    level[nod] = 1 + level[tata];
    for (auto it : edg[nod]){
        int vecin = it.first, cost = it.second;
        if (vecin != tata){
            dp[0][vecin] = make_pair(cost,nod);
            dfs (vecin,nod);
            E[++k] = nod;
        }}}

int get_lca (int x, int y){
    int pozx = first[x], pozy = first[y];
    if (pozx > pozy)
        swap (pozx,pozy);
    int nr = p[pozy-pozx+1];
    pair <int,int> sol = min (rmq[nr][pozx],rmq[nr][pozy-(1<<nr)+1]);
    return E[sol.second];
}

int get_min (int x, int lca){

    int sol = INF;
    for (int i=20;i>=0;i--){
        int y = dp[i][x].second;
        if (level[y] < level[lca])
            continue;

        sol = min (sol,dp[i][x].first);
        x = y;
    }
    return sol;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=m;i++){
        cin>>x>>y>>cost;
        L[x].push_back(make_pair(y,cost));
        L[y].push_back(make_pair(x,cost));
    }

    for (i=1;i<=n;i++)
        dist[i] = INF;

    cin>>cnt;
    for (i=1;i<=cnt;i++){
        cin>>v[i];
        h.push(make_pair(0,v[i]));
        dist[v[i]] = 0;
    }

    while (!h.empty()){
        int nod = h.top().second;
        int cost = h.top().first;
        h.pop();
        if (dist[nod] != cost)
            continue;
        for (auto it : L[nod]){
            int vecin = it.first, new_cost = it.second;
            if (dist[nod] + new_cost < dist[vecin]){
                dist[vecin] = dist[nod] + new_cost;
                h.push(make_pair(dist[vecin],vecin));
            }}}

    /*cin>>q;
    for (i=1;i<=q;i++)
        cin>>qry[i].first>>qry[i].second;*/

    for (i=1;i<=n;i++){
        for (auto it : L[i]){
            int vecin = it.first;
            mch.push_back({i,vecin,min(dist[i],dist[vecin])});
        }
    }

    sort (mch.begin(),mch.end(),cmp);
    memset (t,-1,sizeof t);

    for (auto it : mch){
        int x = it.x, y = it.y;
        int radx = get_rad(x), rady = get_rad(y);
        if (radx != rady){
            //cout<<x<<" "<<y<<" "<<it.cost<<"\n";
            edg[x].push_back(make_pair(y,it.cost));
            edg[y].push_back(make_pair(x,it.cost));

            if (t[radx] > t[rady])
                swap (radx,rady);
            t[radx] += t[rady];
            t[rady] = radx;
        }
    }

    dfs (1,0);

    for (i=1;i<=k;i++)
        rmq[0][i] = make_pair(level[E[i]],i);

    for (i=1;(1<<i)<=k;i++)
        for (j=1;j<=k;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }

    for (i=2;i<=k;i++)
        p[i] = p[i/2] + 1;

    for (i=1;(1<<i)<=n;i++)
        for (j=1;j<=n;j++){
            dp[i][j].second = dp[i-1][dp[i-1][j].second].second;
            dp[i][j].first = min (dp[i-1][j].first,dp[i-1][dp[i-1][j].second].first);
        }

    cin>>q;
    for (i=1;i<=q;i++){
        cin>>x>>y;
        int lca = get_lca (x,y);

        cout<<min(get_min(x,lca),get_min(y,lca))<<"\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5488 KB Output is correct
2 Correct 8 ms 5996 KB Output is correct
3 Correct 8 ms 5996 KB Output is correct
4 Correct 4 ms 5484 KB Output is correct
5 Correct 9 ms 5996 KB Output is correct
6 Correct 9 ms 5996 KB Output is correct
7 Correct 5 ms 5632 KB Output is correct
8 Correct 4 ms 5612 KB Output is correct
9 Correct 8 ms 5996 KB Output is correct
10 Correct 9 ms 5996 KB Output is correct
11 Correct 9 ms 5996 KB Output is correct
12 Correct 9 ms 5996 KB Output is correct
13 Correct 9 ms 5996 KB Output is correct
14 Correct 9 ms 5996 KB Output is correct
15 Correct 9 ms 5996 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5488 KB Output is correct
2 Correct 8 ms 5996 KB Output is correct
3 Correct 8 ms 5996 KB Output is correct
4 Correct 4 ms 5484 KB Output is correct
5 Correct 9 ms 5996 KB Output is correct
6 Correct 9 ms 5996 KB Output is correct
7 Correct 5 ms 5632 KB Output is correct
8 Correct 4 ms 5612 KB Output is correct
9 Correct 8 ms 5996 KB Output is correct
10 Correct 9 ms 5996 KB Output is correct
11 Correct 9 ms 5996 KB Output is correct
12 Correct 9 ms 5996 KB Output is correct
13 Correct 9 ms 5996 KB Output is correct
14 Correct 9 ms 5996 KB Output is correct
15 Correct 9 ms 5996 KB Output is correct
16 Correct 645 ms 52144 KB Output is correct
17 Correct 1344 ms 88656 KB Output is correct
18 Correct 98 ms 13632 KB Output is correct
19 Correct 587 ms 64220 KB Output is correct
20 Correct 1330 ms 88492 KB Output is correct
21 Correct 842 ms 69840 KB Output is correct
22 Correct 646 ms 68480 KB Output is correct
23 Correct 1349 ms 88740 KB Output is correct
24 Correct 1342 ms 88768 KB Output is correct
25 Correct 1324 ms 88768 KB Output is correct
26 Correct 576 ms 64108 KB Output is correct
27 Correct 574 ms 64092 KB Output is correct
28 Correct 573 ms 63964 KB Output is correct
29 Correct 574 ms 64092 KB Output is correct
30 Correct 577 ms 64220 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 67720 KB Output is correct
2 Correct 882 ms 86848 KB Output is correct
3 Correct 903 ms 86976 KB Output is correct
4 Correct 202 ms 64116 KB Output is correct
5 Correct 890 ms 87232 KB Output is correct
6 Correct 879 ms 87040 KB Output is correct
7 Correct 867 ms 86788 KB Output is correct
8 Correct 894 ms 86848 KB Output is correct
9 Correct 895 ms 87160 KB Output is correct
10 Correct 887 ms 86856 KB Output is correct
11 Correct 897 ms 86976 KB Output is correct
12 Correct 894 ms 86976 KB Output is correct
13 Correct 879 ms 86908 KB Output is correct
14 Correct 883 ms 86976 KB Output is correct
15 Correct 894 ms 87148 KB Output is correct
16 Correct 891 ms 86976 KB Output is correct
17 Correct 894 ms 86848 KB Output is correct
18 Correct 887 ms 86848 KB Output is correct
19 Correct 208 ms 66016 KB Output is correct
20 Correct 873 ms 86976 KB Output is correct
21 Correct 845 ms 87488 KB Output is correct
22 Correct 193 ms 62428 KB Output is correct
23 Correct 213 ms 61672 KB Output is correct
24 Correct 201 ms 62428 KB Output is correct
25 Correct 195 ms 62428 KB Output is correct
26 Correct 246 ms 61920 KB Output is correct
27 Correct 213 ms 65760 KB Output is correct
28 Correct 197 ms 62428 KB Output is correct
29 Correct 200 ms 64864 KB Output is correct
30 Correct 196 ms 62428 KB Output is correct
31 Correct 204 ms 64864 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5488 KB Output is correct
2 Correct 8 ms 5996 KB Output is correct
3 Correct 8 ms 5996 KB Output is correct
4 Correct 4 ms 5484 KB Output is correct
5 Correct 9 ms 5996 KB Output is correct
6 Correct 9 ms 5996 KB Output is correct
7 Correct 5 ms 5632 KB Output is correct
8 Correct 4 ms 5612 KB Output is correct
9 Correct 8 ms 5996 KB Output is correct
10 Correct 9 ms 5996 KB Output is correct
11 Correct 9 ms 5996 KB Output is correct
12 Correct 9 ms 5996 KB Output is correct
13 Correct 9 ms 5996 KB Output is correct
14 Correct 9 ms 5996 KB Output is correct
15 Correct 9 ms 5996 KB Output is correct
16 Correct 645 ms 52144 KB Output is correct
17 Correct 1344 ms 88656 KB Output is correct
18 Correct 98 ms 13632 KB Output is correct
19 Correct 587 ms 64220 KB Output is correct
20 Correct 1330 ms 88492 KB Output is correct
21 Correct 842 ms 69840 KB Output is correct
22 Correct 646 ms 68480 KB Output is correct
23 Correct 1349 ms 88740 KB Output is correct
24 Correct 1342 ms 88768 KB Output is correct
25 Correct 1324 ms 88768 KB Output is correct
26 Correct 576 ms 64108 KB Output is correct
27 Correct 574 ms 64092 KB Output is correct
28 Correct 573 ms 63964 KB Output is correct
29 Correct 574 ms 64092 KB Output is correct
30 Correct 577 ms 64220 KB Output is correct
31 Correct 4 ms 5484 KB Output is correct
32 Correct 4 ms 5484 KB Output is correct
33 Correct 4 ms 5484 KB Output is correct
34 Correct 4 ms 5484 KB Output is correct
35 Correct 4 ms 5484 KB Output is correct
36 Correct 4 ms 5484 KB Output is correct
37 Correct 4 ms 5484 KB Output is correct
38 Correct 4 ms 5484 KB Output is correct
39 Correct 4 ms 5484 KB Output is correct
40 Correct 4 ms 5484 KB Output is correct
41 Correct 416 ms 67720 KB Output is correct
42 Correct 882 ms 86848 KB Output is correct
43 Correct 903 ms 86976 KB Output is correct
44 Correct 202 ms 64116 KB Output is correct
45 Correct 890 ms 87232 KB Output is correct
46 Correct 879 ms 87040 KB Output is correct
47 Correct 867 ms 86788 KB Output is correct
48 Correct 894 ms 86848 KB Output is correct
49 Correct 895 ms 87160 KB Output is correct
50 Correct 887 ms 86856 KB Output is correct
51 Correct 897 ms 86976 KB Output is correct
52 Correct 894 ms 86976 KB Output is correct
53 Correct 879 ms 86908 KB Output is correct
54 Correct 883 ms 86976 KB Output is correct
55 Correct 894 ms 87148 KB Output is correct
56 Correct 891 ms 86976 KB Output is correct
57 Correct 894 ms 86848 KB Output is correct
58 Correct 887 ms 86848 KB Output is correct
59 Correct 208 ms 66016 KB Output is correct
60 Correct 873 ms 86976 KB Output is correct
61 Correct 845 ms 87488 KB Output is correct
62 Correct 193 ms 62428 KB Output is correct
63 Correct 213 ms 61672 KB Output is correct
64 Correct 201 ms 62428 KB Output is correct
65 Correct 195 ms 62428 KB Output is correct
66 Correct 246 ms 61920 KB Output is correct
67 Correct 213 ms 65760 KB Output is correct
68 Correct 197 ms 62428 KB Output is correct
69 Correct 200 ms 64864 KB Output is correct
70 Correct 196 ms 62428 KB Output is correct
71 Correct 204 ms 64864 KB Output is correct
72 Correct 854 ms 69532 KB Output is correct
73 Correct 1302 ms 88632 KB Output is correct
74 Correct 1319 ms 89024 KB Output is correct
75 Correct 1306 ms 88512 KB Output is correct
76 Correct 1291 ms 88708 KB Output is correct
77 Correct 1293 ms 88768 KB Output is correct
78 Correct 1286 ms 88584 KB Output is correct
79 Correct 1312 ms 88768 KB Output is correct
80 Correct 1294 ms 88876 KB Output is correct
81 Correct 1305 ms 88640 KB Output is correct
82 Correct 1319 ms 88524 KB Output is correct
83 Correct 1284 ms 88640 KB Output is correct
84 Correct 1292 ms 88600 KB Output is correct
85 Correct 1279 ms 88516 KB Output is correct
86 Correct 1357 ms 88504 KB Output is correct
87 Correct 1335 ms 88664 KB Output is correct
88 Correct 1322 ms 88768 KB Output is correct
89 Correct 732 ms 67296 KB Output is correct
90 Correct 1336 ms 88640 KB Output is correct
91 Correct 1265 ms 89280 KB Output is correct
92 Correct 610 ms 64092 KB Output is correct
93 Correct 683 ms 63848 KB Output is correct
94 Correct 616 ms 63836 KB Output is correct
95 Correct 625 ms 64092 KB Output is correct
96 Correct 683 ms 63836 KB Output is correct
97 Correct 726 ms 65888 KB Output is correct
98 Correct 624 ms 63964 KB Output is correct
99 Correct 731 ms 67424 KB Output is correct
100 Correct 617 ms 63964 KB Output is correct