oj.uz

Submission #552703

# Submission time Handle Problem Language Result Execution time Memory
552703 2022-04-23T16:25:34 Z Magi Swapping Cities (APIO20_swap) C++14
36 / 100
 759 ms 53224 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], dpCycle[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;

    dpCycle[x] = inf;
    for(auto u : nod[x])
        if(dp[0][u.f] != x && dp[0][x] != u.f)
            dpCycle[x] = min(dpCycle[x], u.s);

    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};
            }

            dpCycle[x] = min(dpCycle[x], dpCycle[u.f]);
        }
}

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]);

        val2 = min(val2, dpCycle[y]);

    }

    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]));

        val2 = min(val2, dpCycle[x]);
        val2 = min(val2, dpCycle[y]);
    }

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5000 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5376 KB Output is correct
5 Correct 4 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 5 ms 5472 KB Output is correct
9 Correct 143 ms 36332 KB Output is correct
10 Correct 206 ms 44580 KB Output is correct
11 Correct 227 ms 43388 KB Output is correct
12 Correct 205 ms 45668 KB Output is correct
13 Correct 148 ms 47552 KB Output is correct
14 Correct 198 ms 35812 KB Output is correct
15 Correct 636 ms 46336 KB Output is correct
16 Correct 690 ms 43764 KB Output is correct
17 Correct 609 ms 49220 KB Output is correct
18 Correct 609 ms 47836 KB Output is correct
19 Correct 149 ms 14864 KB Output is correct
20 Correct 647 ms 51140 KB Output is correct
21 Correct 683 ms 49084 KB Output is correct
22 Correct 755 ms 52764 KB Output is correct
23 Correct 642 ms 53224 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5000 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 267 ms 42708 KB Output is correct
4 Correct 239 ms 44176 KB Output is correct
5 Correct 276 ms 43428 KB Output is correct
6 Correct 251 ms 44048 KB Output is correct
7 Correct 239 ms 43968 KB Output is correct
8 Correct 241 ms 42604 KB Output is correct
9 Correct 208 ms 43624 KB Output is correct
10 Correct 225 ms 42064 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5000 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5376 KB Output is correct
5 Correct 4 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 5 ms 5472 KB Output is correct
9 Correct 4 ms 5076 KB Output is correct
10 Correct 4 ms 5460 KB Output is correct
11 Correct 4 ms 5460 KB Output is correct
12 Correct 4 ms 5480 KB Output is correct
13 Correct 4 ms 5332 KB Output is correct
14 Correct 5 ms 5460 KB Output is correct
15 Correct 4 ms 5460 KB Output is correct
16 Correct 4 ms 5460 KB Output is correct
17 Correct 4 ms 5460 KB Output is correct
18 Correct 5 ms 5460 KB Output is correct
19 Correct 5 ms 5360 KB Output is correct
20 Correct 5 ms 5460 KB Output is correct
21 Correct 5 ms 5460 KB Output is correct
22 Correct 6 ms 5332 KB Output is correct
23 Correct 4 ms 5460 KB Output is correct
24 Incorrect 6 ms 5460 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5376 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 5 ms 5472 KB Output is correct
10 Correct 143 ms 36332 KB Output is correct
11 Correct 206 ms 44580 KB Output is correct
12 Correct 227 ms 43388 KB Output is correct
13 Correct 205 ms 45668 KB Output is correct
14 Correct 148 ms 47552 KB Output is correct
15 Correct 4 ms 5460 KB Output is correct
16 Correct 4 ms 5460 KB Output is correct
17 Correct 4 ms 5480 KB Output is correct
18 Correct 4 ms 5332 KB Output is correct
19 Correct 5 ms 5460 KB Output is correct
20 Correct 4 ms 5460 KB Output is correct
21 Correct 4 ms 5460 KB Output is correct
22 Correct 4 ms 5460 KB Output is correct
23 Correct 5 ms 5460 KB Output is correct
24 Correct 5 ms 5360 KB Output is correct
25 Correct 5 ms 5460 KB Output is correct
26 Correct 5 ms 5460 KB Output is correct
27 Correct 6 ms 5332 KB Output is correct
28 Correct 4 ms 5460 KB Output is correct
29 Incorrect 6 ms 5460 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5000 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5376 KB Output is correct
5 Correct 4 ms 5460 KB Output is correct
6 Correct 5 ms 5460 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 5 ms 5472 KB Output is correct
9 Correct 143 ms 36332 KB Output is correct
10 Correct 206 ms 44580 KB Output is correct
11 Correct 227 ms 43388 KB Output is correct
12 Correct 205 ms 45668 KB Output is correct
13 Correct 148 ms 47552 KB Output is correct
14 Correct 198 ms 35812 KB Output is correct
15 Correct 636 ms 46336 KB Output is correct
16 Correct 690 ms 43764 KB Output is correct
17 Correct 609 ms 49220 KB Output is correct
18 Correct 609 ms 47836 KB Output is correct
19 Correct 267 ms 42708 KB Output is correct
20 Correct 239 ms 44176 KB Output is correct
21 Correct 276 ms 43428 KB Output is correct
22 Correct 251 ms 44048 KB Output is correct
23 Correct 239 ms 43968 KB Output is correct
24 Correct 241 ms 42604 KB Output is correct
25 Correct 208 ms 43624 KB Output is correct
26 Correct 225 ms 42064 KB Output is correct
27 Correct 4 ms 5460 KB Output is correct
28 Correct 4 ms 5460 KB Output is correct
29 Correct 4 ms 5480 KB Output is correct
30 Correct 4 ms 5332 KB Output is correct
31 Correct 5 ms 5460 KB Output is correct
32 Correct 4 ms 5460 KB Output is correct
33 Correct 4 ms 5460 KB Output is correct
34 Correct 4 ms 5460 KB Output is correct
35 Correct 5 ms 5460 KB Output is correct
36 Correct 16 ms 9648 KB Output is correct
37 Correct 190 ms 45168 KB Output is correct
38 Correct 234 ms 42668 KB Output is correct
39 Correct 176 ms 40772 KB Output is correct
40 Correct 159 ms 40100 KB Output is correct
41 Correct 191 ms 39576 KB Output is correct
42 Correct 166 ms 37120 KB Output is correct
43 Correct 170 ms 43332 KB Output is correct
44 Correct 183 ms 44588 KB Output is correct
45 Correct 170 ms 45808 KB Output is correct
46 Correct 180 ms 40816 KB Output is correct
47 Correct 36 ms 9548 KB Output is correct
48 Correct 759 ms 45880 KB Output is correct
49 Correct 715 ms 44576 KB Output is correct
50 Correct 695 ms 43584 KB Output is correct
51 Correct 594 ms 42960 KB Output is correct
52 Correct 582 ms 40704 KB Output is correct
53 Correct 364 ms 32624 KB Output is correct
54 Correct 738 ms 45896 KB Output is correct
55 Correct 687 ms 46660 KB Output is correct
56 Correct 575 ms 49188 KB Output is correct
57 Correct 535 ms 44140 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 4 ms 5376 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 5 ms 5460 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 5 ms 5472 KB Output is correct
10 Correct 143 ms 36332 KB Output is correct
11 Correct 206 ms 44580 KB Output is correct
12 Correct 227 ms 43388 KB Output is correct
13 Correct 205 ms 45668 KB Output is correct
14 Correct 148 ms 47552 KB Output is correct
15 Correct 198 ms 35812 KB Output is correct
16 Correct 636 ms 46336 KB Output is correct
17 Correct 690 ms 43764 KB Output is correct
18 Correct 609 ms 49220 KB Output is correct
19 Correct 609 ms 47836 KB Output is correct
20 Correct 267 ms 42708 KB Output is correct
21 Correct 239 ms 44176 KB Output is correct
22 Correct 276 ms 43428 KB Output is correct
23 Correct 251 ms 44048 KB Output is correct
24 Correct 239 ms 43968 KB Output is correct
25 Correct 241 ms 42604 KB Output is correct
26 Correct 208 ms 43624 KB Output is correct
27 Correct 225 ms 42064 KB Output is correct
28 Correct 4 ms 5460 KB Output is correct
29 Correct 4 ms 5460 KB Output is correct
30 Correct 4 ms 5480 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct
32 Correct 5 ms 5460 KB Output is correct
33 Correct 4 ms 5460 KB Output is correct
34 Correct 4 ms 5460 KB Output is correct
35 Correct 4 ms 5460 KB Output is correct
36 Correct 5 ms 5460 KB Output is correct
37 Correct 16 ms 9648 KB Output is correct
38 Correct 190 ms 45168 KB Output is correct
39 Correct 234 ms 42668 KB Output is correct
40 Correct 176 ms 40772 KB Output is correct
41 Correct 159 ms 40100 KB Output is correct
42 Correct 191 ms 39576 KB Output is correct
43 Correct 166 ms 37120 KB Output is correct
44 Correct 170 ms 43332 KB Output is correct
45 Correct 183 ms 44588 KB Output is correct
46 Correct 170 ms 45808 KB Output is correct
47 Correct 180 ms 40816 KB Output is correct
48 Correct 36 ms 9548 KB Output is correct
49 Correct 759 ms 45880 KB Output is correct
50 Correct 715 ms 44576 KB Output is correct
51 Correct 695 ms 43584 KB Output is correct
52 Correct 594 ms 42960 KB Output is correct
53 Correct 582 ms 40704 KB Output is correct
54 Correct 364 ms 32624 KB Output is correct
55 Correct 738 ms 45896 KB Output is correct
56 Correct 687 ms 46660 KB Output is correct
57 Correct 575 ms 49188 KB Output is correct
58 Correct 535 ms 44140 KB Output is correct
59 Correct 149 ms 14864 KB Output is correct
60 Correct 647 ms 51140 KB Output is correct
61 Correct 683 ms 49084 KB Output is correct
62 Correct 755 ms 52764 KB Output is correct
63 Correct 642 ms 53224 KB Output is correct
64 Correct 5 ms 5360 KB Output is correct
65 Correct 5 ms 5460 KB Output is correct
66 Correct 5 ms 5460 KB Output is correct
67 Correct 6 ms 5332 KB Output is correct
68 Correct 4 ms 5460 KB Output is correct
69 Incorrect 6 ms 5460 KB Output isn't correct
70 Halted 0 ms 0 KB -