oj.uz

Submission #552646

# Submission time Handle Problem Language Result Execution time Memory
552646 2022-04-23T13:27:00 Z Magi Swapping Cities (APIO20_swap) C++14
7 / 100
 518 ms 45956 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(mini[2][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, dp_sus[LCA.f]);


    }

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

Compilation message

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

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 5016 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 4 ms 5460 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 4 ms 5420 KB Output is correct
8 Correct 4 ms 5404 KB Output is correct
9 Correct 113 ms 34348 KB Output is correct
10 Correct 154 ms 41664 KB Output is correct
11 Correct 129 ms 40724 KB Output is correct
12 Correct 144 ms 42828 KB Output is correct
13 Correct 154 ms 44124 KB Output is correct
14 Correct 141 ms 33776 KB Output is correct
15 Correct 440 ms 43484 KB Output is correct
16 Correct 518 ms 41264 KB Output is correct
17 Correct 466 ms 45956 KB Output is correct
18 Correct 429 ms 44832 KB Output is correct
19 Incorrect 132 ms 13388 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 169 ms 41012 KB Output is correct
4 Correct 197 ms 42428 KB Output is correct
5 Correct 175 ms 41896 KB Output is correct
6 Correct 185 ms 42352 KB Output is correct
7 Correct 177 ms 42220 KB Output is correct
8 Correct 181 ms 40700 KB Output is correct
9 Correct 174 ms 41916 KB Output is correct
10 Correct 186 ms 40520 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 5016 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 4 ms 5460 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 4 ms 5420 KB Output is correct
8 Correct 4 ms 5404 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
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 5016 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 4 ms 5460 KB Output is correct
6 Correct 4 ms 5460 KB Output is correct
7 Correct 4 ms 5420 KB Output is correct
8 Correct 4 ms 5404 KB Output is correct
9 Correct 113 ms 34348 KB Output is correct
10 Correct 154 ms 41664 KB Output is correct
11 Correct 129 ms 40724 KB Output is correct
12 Correct 144 ms 42828 KB Output is correct
13 Correct 154 ms 44124 KB Output is correct
14 Correct 141 ms 33776 KB Output is correct
15 Correct 440 ms 43484 KB Output is correct
16 Correct 518 ms 41264 KB Output is correct
17 Correct 466 ms 45956 KB Output is correct
18 Correct 429 ms 44832 KB Output is correct
19 Correct 169 ms 41012 KB Output is correct
20 Correct 197 ms 42428 KB Output is correct
21 Correct 175 ms 41896 KB Output is correct
22 Correct 185 ms 42352 KB Output is correct
23 Correct 177 ms 42220 KB Output is correct
24 Correct 181 ms 40700 KB Output is correct
25 Correct 174 ms 41916 KB Output is correct
26 Correct 186 ms 40520 KB Output is correct
27 Correct 5 ms 5332 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 5332 KB Output is correct
31 Correct 4 ms 5404 KB Output is correct
32 Correct 4 ms 5412 KB Output is correct
33 Incorrect 4 ms 5460 KB Output isn't correct
34 Halted 0 ms 0 KB -

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 -