oj.uz

Submission #552621

# Submission time Handle Problem Language Result Execution time Memory
552621 2022-04-23T12:38:06 Z Magi Swapping Cities (APIO20_swap) C++14
7 / 100
 489 ms 45340 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;
        val2 = min(val2, minLant(x, val));

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

    }

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

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


    }

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

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:189:48: warning: unused variable 'costVal1' [-Wunused-variable]
  189 |         int val = nivel[x] - nivel[LCA.f] - 1, costVal1 = costTata[findStr(x, val)];
      |                                                ^~~~~~~~
swap.cpp:193:13: warning: unused variable 'costVal2' [-Wunused-variable]
  193 |         int costVal2 = costTata[findStr(y, val)];
      |             ^~~~~~~~

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 5204 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 83 ms 33700 KB Output is correct
10 Correct 132 ms 41196 KB Output is correct
11 Correct 108 ms 40176 KB Output is correct
12 Correct 115 ms 42164 KB Output is correct
13 Correct 110 ms 43548 KB Output is correct
14 Correct 133 ms 33356 KB Output is correct
15 Correct 426 ms 42964 KB Output is correct
16 Correct 489 ms 40708 KB Output is correct
17 Correct 398 ms 45340 KB Output is correct
18 Correct 402 ms 44316 KB Output is correct
19 Incorrect 102 ms 13104 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 159 ms 40456 KB Output is correct
4 Correct 169 ms 41860 KB Output is correct
5 Correct 183 ms 41136 KB Output is correct
6 Correct 165 ms 41876 KB Output is correct
7 Correct 208 ms 41640 KB Output is correct
8 Correct 178 ms 40204 KB Output is correct
9 Correct 167 ms 41352 KB Output is correct
10 Correct 165 ms 40000 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 5204 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 4 ms 5460 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
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 5204 KB Output is correct
5 Correct 3 ms 5460 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 4 ms 5460 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 83 ms 33700 KB Output is correct
10 Correct 132 ms 41196 KB Output is correct
11 Correct 108 ms 40176 KB Output is correct
12 Correct 115 ms 42164 KB Output is correct
13 Correct 110 ms 43548 KB Output is correct
14 Correct 133 ms 33356 KB Output is correct
15 Correct 426 ms 42964 KB Output is correct
16 Correct 489 ms 40708 KB Output is correct
17 Correct 398 ms 45340 KB Output is correct
18 Correct 402 ms 44316 KB Output is correct
19 Correct 159 ms 40456 KB Output is correct
20 Correct 169 ms 41860 KB Output is correct
21 Correct 183 ms 41136 KB Output is correct
22 Correct 165 ms 41876 KB Output is correct
23 Correct 208 ms 41640 KB Output is correct
24 Correct 178 ms 40204 KB Output is correct
25 Correct 167 ms 41352 KB Output is correct
26 Correct 165 ms 40000 KB Output is correct
27 Correct 5 ms 5332 KB Output is correct
28 Correct 5 ms 5332 KB Output is correct
29 Correct 4 ms 5332 KB Output is correct
30 Correct 3 ms 5332 KB Output is correct
31 Correct 3 ms 5332 KB Output is correct
32 Incorrect 4 ms 5332 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 -