oj.uz

Submission #552193

# Submission time Handle Problem Language Result Execution time Memory
552193 2022-04-22T16:16:51 Z Magi Swapping Cities (APIO20_swap) C++14
7 / 100
 543 ms 49844 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];
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 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] = 0;
    dfs(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, costVal = costTata[findStr(x, val)];
        val2 = min(val2, minLant(x, val));

        int c = 0, valx = 0;
        bool ok = false;
        for(int t=0; t<3 && c<2; t++){
            if(!ok && costVal == mini[t][y])
                ok = true;
            else
                c++, valx = max(valx, mini[t][y]);
        }

        val2 = min(val2, valx);

    }

    else{
        val2 = min(mini[1][x], mini[1][y]);

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

        bool ok1 = false, ok2 = false;
        for(int t=0; t<3; t++){
            if(!ok1 && costVal1 == mini[t][LCA.f])
                ok1 = true;
            else if(!ok2 && costVal2 == mini[t][LCA.f])
                ok2 = true;
            else{
                val2 = min(val2, mini[t][LCA.f]);
                break;
            }
        }

    }

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5124 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 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 5428 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 89 ms 35404 KB Output is correct
10 Correct 136 ms 43132 KB Output is correct
11 Correct 122 ms 42200 KB Output is correct
12 Correct 130 ms 44308 KB Output is correct
13 Correct 115 ms 45784 KB Output is correct
14 Correct 133 ms 35176 KB Output is correct
15 Correct 528 ms 47360 KB Output is correct
16 Correct 521 ms 44988 KB Output is correct
17 Correct 485 ms 49844 KB Output is correct
18 Correct 543 ms 48688 KB Output is correct
19 Incorrect 131 ms 15056 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 5124 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 183 ms 40592 KB Output is correct
4 Correct 187 ms 41840 KB Output is correct
5 Correct 198 ms 41152 KB Output is correct
6 Correct 176 ms 41808 KB Output is correct
7 Correct 207 ms 41756 KB Output is correct
8 Correct 176 ms 40304 KB Output is correct
9 Correct 201 ms 41420 KB Output is correct
10 Correct 208 ms 39920 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5124 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 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 5428 KB Output is correct
8 Correct 5 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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5124 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 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 5428 KB Output is correct
8 Correct 5 ms 5460 KB Output is correct
9 Correct 89 ms 35404 KB Output is correct
10 Correct 136 ms 43132 KB Output is correct
11 Correct 122 ms 42200 KB Output is correct
12 Correct 130 ms 44308 KB Output is correct
13 Correct 115 ms 45784 KB Output is correct
14 Correct 133 ms 35176 KB Output is correct
15 Correct 528 ms 47360 KB Output is correct
16 Correct 521 ms 44988 KB Output is correct
17 Correct 485 ms 49844 KB Output is correct
18 Correct 543 ms 48688 KB Output is correct
19 Correct 183 ms 40592 KB Output is correct
20 Correct 187 ms 41840 KB Output is correct
21 Correct 198 ms 41152 KB Output is correct
22 Correct 176 ms 41808 KB Output is correct
23 Correct 207 ms 41756 KB Output is correct
24 Correct 176 ms 40304 KB Output is correct
25 Correct 201 ms 41420 KB Output is correct
26 Correct 208 ms 39920 KB Output is correct
27 Correct 4 ms 5372 KB Output is correct
28 Correct 5 ms 5408 KB Output is correct
29 Correct 4 ms 5408 KB Output is correct
30 Correct 4 ms 5404 KB Output is correct
31 Correct 4 ms 5408 KB Output is correct
32 Incorrect 4 ms 5428 KB Output isn't correct
33 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 -