oj.uz

Submission #552701

# Submission time Handle Problem Language Result Execution time Memory
552701 2022-04-23T16:14:53 Z Magi Swapping Cities (APIO20_swap) C++14
30 / 100
 528 ms 52860 KB 
#include "swap.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second

using namespace std;

const int NMAX = 1e5, MMAX = 2e5, inf = 2e9;
int n, m, tata[NMAX+10], rang[NMAX+10], mini[3][NMAX+10], costTata[NMAX+10], dp[20][NMAX+10], dp1[20][NMAX+10], dp2[20][NMAX+10], nivel[NMAX+10];
int dp_sus[NMAX+10];
pair <int, int> dp_jos[2][NMAX+10];

vector <pair <int, int> > nod[NMAX+10], tree[NMAX+10];

struct Kruskal{
    int n1, n2, cost;
}K[MMAX+10];

inline bool cmp(Kruskal a, Kruskal b){
    return a.cost < b.cost;
}

int findDaddy(int x){
    int r = x, y = x;
    while(r != tata[r])
        r = tata[r];
    while(x != tata[x]){
        y = tata[x];
        tata[x] = r;
        x = y;
    }
    return r;
}

void unite(int x, int y){

    if(rang[x] < rang[y])
        tata[x] = y;
    else
        tata[y] = x;
    if(rang[x] == rang[y])
        rang[x]++;
}

void dfs(int x, int p = 0){

    dp[0][x] = p;
    nivel[x] = nivel[p] + 1;

    for(auto u : nod[x])
        if(u.f != p){

            for(int t=0; t<3; t++)
                if(mini[t][x] > u.s){
                    for(int t1=2; t1>t; t1--)
                        mini[t1][x] = mini[t1-1][x];
                    mini[t][x] = u.s;
                    break;
                }
        }

    for(auto u : tree[x])
        if(u.f != p){
            dfs(u.f, x);
            costTata[u.f] = u.s;
        }
}

void dfs1(int x, int p = 0){

    dp_jos[0][x].f = dp_jos[0][x].s = dp_jos[1][x].f = dp_jos[1][x].s = inf;

    for(auto u : tree[x])
        if(u.f != p){
            dfs1(u.f, x);

            if(max(u.s, min(dp_jos[0][u.f].f, mini[1][u.f])) < dp_jos[0][x].f){
                dp_jos[1][x] = dp_jos[0][x];
                dp_jos[0][x] = {max(u.s, min(dp_jos[0][u.f].f, mini[1][u.f])), u.s};
            }

            else if(max(u.s, min(dp_jos[0][u.f].f, mini[1][u.f])) < dp_jos[1][x].f){
                dp_jos[1][x] = {max(u.s, min(dp_jos[0][u.f].f, mini[1][u.f])), u.s};
            }
        }
}

void dfs2(int x, int p = 0){

    dp_sus[x] = min(min(mini[2][x], max(mini[1][x], costTata[x])), max(costTata[x], dp_sus[dp[0][x]]));
    if(dp_jos[0][dp[0][x]].s == x)
        dp_sus[x] = min(dp_sus[x], max(costTata[x], dp_jos[1][dp[0][x]].f));
    else
        dp_sus[x] = min(dp_sus[x], max(costTata[x], dp_jos[0][dp[0][x]].f));

    for(auto u : tree[x])
        if(u.f != p)
            dfs2(u.f, x);
}

void buildStramosi(){

    for(int i=1; i<=n; i++){
        if(costTata[i] != mini[0][dp[0][i]])
            dp2[0][i] = mini[0][dp[0][i]];
        else
            dp2[0][i] = mini[1][dp[0][i]];

        dp1[0][i] = costTata[i];
    }

    for(int bit=1; (1<<bit)<=n; bit++)
        for(int i=1; i<=n; i++){
            dp[bit][i] = dp[bit-1][dp[bit-1][i]];
            dp1[bit][i] = max(dp1[bit-1][i], dp1[bit-1][dp[bit-1][i]]);
            dp2[bit][i] = min(dp2[bit-1][i], dp2[bit-1][dp[bit-1][i]]);
        }

}

pair <int, int> lca(int x, int y){

    if(nivel[x] < nivel[y])
        swap(x, y);
    int dif = nivel[x] - nivel[y], ans = 0;

    for(int bit=0; (1<<bit)<=dif; bit++)
        if(dif & (1 << bit)){
            ans = max(ans, dp1[bit][x]);
            x = dp[bit][x];
        }

    if(x == y)
        return {x, ans};
    for(int bit=19; bit>=0; bit--)
        if(dp[bit][x] != dp[bit][y]){
            ans = max(ans, max(dp1[bit][x], dp1[bit][y]));
            x = dp[bit][x];
            y = dp[bit][y];
        }

    return {dp[0][x], max(ans, max(dp1[0][x], dp1[0][y]))};

}

int findStr(int x, int k){
    for(int bit=0; (1<<bit)<=k; bit++)
        if(k & (1 << bit))
            x = dp[bit][x];
    return x;
}

int minLant(int x, int k){
    int ans = inf;
    for(int bit=0; (1<<bit)<=k; bit++)
        if(k & (1 << bit)){
            ans = min(ans, dp2[bit][x]);
            x = dp[bit][x];
        }
    return ans;
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W){

    n = N;
    m = M;

    for(int i=1; i<=n; i++)
        tata[i] = i, rang[i] = 1;

    for(int i=0; i<m; i++){
        int nod1 = U[i] + 1, nod2 = V[i] + 1, cost = W[i];
        nod[nod1].push_back({nod2, cost});
        nod[nod2].push_back({nod1, cost});

        K[i+1] = {nod1, nod2, cost};
    }

    sort(K+1, K+m+1, cmp);

    for(int i=1; i<=m; i++){
        int val1 = findDaddy(K[i].n1), val2 = findDaddy(K[i].n2);
        if(val1 != val2){
            unite(val1, val2);
            tree[K[i].n1].push_back({K[i].n2, K[i].cost});
            tree[K[i].n2].push_back({K[i].n1, K[i].cost});
        }
    }

    for(int i=1; i<=n; i++)
        mini[0][i] = mini[1][i] = mini[2][i] = inf;

    costTata[1] = inf;
    dfs(1);
    dfs1(1);
    dfs2(1);

    buildStramosi();

}

int getMinimumFuelCapacity(int X, int Y){

    int x = X + 1, y = Y + 1;
    pair <int, int> LCA = lca(x, y);
    int val1 = LCA.s, val2 = inf;

    if(findStr(y, nivel[y] - nivel[LCA.f]) == x)
        swap(x, y);

    if(findStr(x, nivel[x] - nivel[LCA.f]) == y){
        val2 = mini[1][x];

        int val = nivel[x] - nivel[LCA.f] - 1, str = findStr(x, val);
        val2 = min(val2, minLant(x, val));

        val2 = min(val2, dp_sus[str]);

    }

    else{
        val2 = min(dp_jos[0][x].f, dp_jos[0][y].f);
        val2 = min(val2, min(mini[1][x], mini[1][y]));

        int val = nivel[x] - nivel[LCA.f] - 1;
        val2 = min(val2, minLant(x, val));
        val = nivel[y] - nivel[LCA.f] - 1;
        val2 = min(val2, minLant(y, val));

        val2 = min(val2, min(mini[2][LCA.f], costTata[LCA.f]));


    }

    if(val2 == inf)
        return -1;
    return max(val1, val2);
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Correct 3 ms 5480 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 101 ms 36016 KB Output is correct
10 Correct 163 ms 44288 KB Output is correct
11 Correct 130 ms 43028 KB Output is correct
12 Correct 141 ms 45356 KB Output is correct
13 Correct 119 ms 47144 KB Output is correct
14 Correct 132 ms 35468 KB Output is correct
15 Correct 491 ms 45944 KB Output is correct
16 Correct 520 ms 43340 KB Output is correct
17 Correct 462 ms 48944 KB Output is correct
18 Correct 503 ms 47540 KB Output is correct
19 Incorrect 114 ms 13688 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 176 ms 42380 KB Output is correct
4 Correct 180 ms 43808 KB Output is correct
5 Correct 179 ms 43104 KB Output is correct
6 Correct 176 ms 43756 KB Output is correct
7 Correct 185 ms 43568 KB Output is correct
8 Correct 183 ms 42124 KB Output is correct
9 Correct 176 ms 43340 KB Output is correct
10 Correct 184 ms 41724 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Correct 3 ms 5480 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Incorrect 3 ms 5076 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 5460 KB Output is correct
7 Correct 3 ms 5480 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 101 ms 36016 KB Output is correct
10 Correct 163 ms 44288 KB Output is correct
11 Correct 130 ms 43028 KB Output is correct
12 Correct 141 ms 45356 KB Output is correct
13 Correct 119 ms 47144 KB Output is correct
14 Correct 132 ms 35468 KB Output is correct
15 Correct 491 ms 45944 KB Output is correct
16 Correct 520 ms 43340 KB Output is correct
17 Correct 462 ms 48944 KB Output is correct
18 Correct 503 ms 47540 KB Output is correct
19 Correct 176 ms 42380 KB Output is correct
20 Correct 180 ms 43808 KB Output is correct
21 Correct 179 ms 43104 KB Output is correct
22 Correct 176 ms 43756 KB Output is correct
23 Correct 185 ms 43568 KB Output is correct
24 Correct 183 ms 42124 KB Output is correct
25 Correct 176 ms 43340 KB Output is correct
26 Correct 184 ms 41724 KB Output is correct
27 Correct 4 ms 5460 KB Output is correct
28 Correct 5 ms 5460 KB Output is correct
29 Correct 3 ms 5460 KB Output is correct
30 Correct 3 ms 5332 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct
32 Correct 4 ms 5460 KB Output is correct
33 Correct 4 ms 5460 KB Output is correct
34 Correct 3 ms 5460 KB Output is correct
35 Correct 5 ms 5460 KB Output is correct
36 Correct 17 ms 9580 KB Output is correct
37 Correct 138 ms 44840 KB Output is correct
38 Correct 155 ms 42280 KB Output is correct
39 Correct 166 ms 40292 KB Output is correct
40 Correct 123 ms 39628 KB Output is correct
41 Correct 131 ms 39196 KB Output is correct
42 Correct 124 ms 36736 KB Output is correct
43 Correct 159 ms 42916 KB Output is correct
44 Correct 137 ms 44212 KB Output is correct
45 Correct 126 ms 45464 KB Output is correct
46 Correct 145 ms 40396 KB Output is correct
47 Correct 26 ms 9536 KB Output is correct
48 Correct 501 ms 49652 KB Output is correct
49 Correct 498 ms 48244 KB Output is correct
50 Correct 498 ms 47100 KB Output is correct
51 Correct 479 ms 46688 KB Output is correct
52 Correct 426 ms 44260 KB Output is correct
53 Correct 279 ms 35904 KB Output is correct
54 Correct 527 ms 49792 KB Output is correct
55 Correct 528 ms 50216 KB Output is correct
56 Correct 514 ms 52860 KB Output is correct
57 Correct 405 ms 48120 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -