oj.uz

Submission #552650

# Submission time Handle Problem Language Result Execution time Memory
552650 2022-04-23T13:35:34 Z Magi Swapping Cities (APIO20_swap) C++14
7 / 100
 557 ms 45760 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], dp_sus[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_sus[x] = min(min(mini[2][x], max(mini[1][x], costTata[x])), max(costTata[x], dp_sus[dp[0][x]]));
    for(auto u : tree[x])
        if(u.f != p)
            dfs1(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);

    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){
        int x1 = x;
        val2 = mini[1][x];

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

        val2 = min(val2, dp_sus[LCA.f]);

    }

    else{
        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);
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:185:13: warning: unused variable 'x1' [-Wunused-variable]
  185 |         int x1 = x;
      |             ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 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 5248 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 109 ms 33980 KB Output is correct
10 Correct 144 ms 41548 KB Output is correct
11 Correct 129 ms 40468 KB Output is correct
12 Correct 144 ms 42544 KB Output is correct
13 Correct 117 ms 43980 KB Output is correct
14 Correct 137 ms 33572 KB Output is correct
15 Correct 464 ms 43260 KB Output is correct
16 Correct 557 ms 41092 KB Output is correct
17 Correct 428 ms 45760 KB Output is correct
18 Correct 430 ms 44684 KB Output is correct
19 Incorrect 120 ms 13136 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 4948 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 180 ms 40832 KB Output is correct
4 Correct 196 ms 42240 KB Output is correct
5 Correct 203 ms 41480 KB Output is correct
6 Correct 166 ms 42120 KB Output is correct
7 Correct 181 ms 41972 KB Output is correct
8 Correct 190 ms 40632 KB Output is correct
9 Correct 174 ms 41800 KB Output is correct
10 Correct 192 ms 40328 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 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 5248 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Incorrect 3 ms 5064 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 5064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 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 5248 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 109 ms 33980 KB Output is correct
10 Correct 144 ms 41548 KB Output is correct
11 Correct 129 ms 40468 KB Output is correct
12 Correct 144 ms 42544 KB Output is correct
13 Correct 117 ms 43980 KB Output is correct
14 Correct 137 ms 33572 KB Output is correct
15 Correct 464 ms 43260 KB Output is correct
16 Correct 557 ms 41092 KB Output is correct
17 Correct 428 ms 45760 KB Output is correct
18 Correct 430 ms 44684 KB Output is correct
19 Correct 180 ms 40832 KB Output is correct
20 Correct 196 ms 42240 KB Output is correct
21 Correct 203 ms 41480 KB Output is correct
22 Correct 166 ms 42120 KB Output is correct
23 Correct 181 ms 41972 KB Output is correct
24 Correct 190 ms 40632 KB Output is correct
25 Correct 174 ms 41800 KB Output is correct
26 Correct 192 ms 40328 KB Output is correct
27 Correct 4 ms 5332 KB Output is correct
28 Correct 3 ms 5332 KB Output is correct
29 Correct 4 ms 5332 KB Output is correct
30 Correct 4 ms 5332 KB Output is correct
31 Correct 3 ms 5332 KB Output is correct
32 Correct 4 ms 5332 KB Output is correct
33 Correct 4 ms 5332 KB Output is correct
34 Correct 5 ms 5460 KB Output is correct
35 Correct 6 ms 5404 KB Output is correct
36 Correct 15 ms 9628 KB Output is correct
37 Correct 126 ms 43980 KB Output is correct
38 Correct 132 ms 41916 KB Output is correct
39 Correct 168 ms 40460 KB Output is correct
40 Correct 127 ms 39812 KB Output is correct
41 Correct 116 ms 39420 KB Output is correct
42 Correct 104 ms 36964 KB Output is correct
43 Incorrect 174 ms 42860 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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