oj.uz

Submission #552620

# Submission time Handle Problem Language Result Execution time Memory
552620 2022-04-23T12:35:22 Z Magi Swapping Cities (APIO20_swap) C++14
7 / 100
 484 ms 49840 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, 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;
            }
        }

    }

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

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:179:48: warning: unused variable 'costVal' [-Wunused-variable]
  179 |         int val = nivel[x] - nivel[LCA.f] - 1, costVal = costTata[findStr(x, val)];
      |                                                ^~~~~~~
swap.cpp:182:13: warning: unused variable 'c' [-Wunused-variable]
  182 |         int c = 0, valx = 0;
      |             ^
swap.cpp:182:20: warning: unused variable 'valx' [-Wunused-variable]
  182 |         int c = 0, valx = 0;
      |                    ^~~~
swap.cpp:183:14: warning: unused variable 'ok' [-Wunused-variable]
  183 |         bool ok = false;
      |              ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB Output is correct
2 Correct 4 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 3 ms 5460 KB Output is correct
7 Correct 3 ms 5412 KB Output is correct
8 Correct 4 ms 5396 KB Output is correct
9 Correct 96 ms 35388 KB Output is correct
10 Correct 115 ms 43196 KB Output is correct
11 Correct 118 ms 42088 KB Output is correct
12 Correct 119 ms 44268 KB Output is correct
13 Correct 126 ms 45720 KB Output is correct
14 Correct 112 ms 35092 KB Output is correct
15 Correct 460 ms 47260 KB Output is correct
16 Correct 484 ms 45160 KB Output is correct
17 Correct 401 ms 49840 KB Output is correct
18 Correct 459 ms 48688 KB Output is correct
19 Incorrect 106 ms 15052 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 5020 KB Output is correct
2 Correct 4 ms 5076 KB Output is correct
3 Correct 199 ms 44388 KB Output is correct
4 Correct 182 ms 45716 KB Output is correct
5 Correct 183 ms 45148 KB Output is correct
6 Correct 173 ms 45504 KB Output is correct
7 Correct 174 ms 45560 KB Output is correct
8 Correct 191 ms 44120 KB Output is correct
9 Correct 173 ms 45188 KB Output is correct
10 Correct 229 ms 43816 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB Output is correct
2 Correct 4 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 3 ms 5460 KB Output is correct
7 Correct 3 ms 5412 KB Output is correct
8 Correct 4 ms 5396 KB Output is correct
9 Incorrect 3 ms 5016 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 5016 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 5020 KB Output is correct
2 Correct 4 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 3 ms 5460 KB Output is correct
7 Correct 3 ms 5412 KB Output is correct
8 Correct 4 ms 5396 KB Output is correct
9 Correct 96 ms 35388 KB Output is correct
10 Correct 115 ms 43196 KB Output is correct
11 Correct 118 ms 42088 KB Output is correct
12 Correct 119 ms 44268 KB Output is correct
13 Correct 126 ms 45720 KB Output is correct
14 Correct 112 ms 35092 KB Output is correct
15 Correct 460 ms 47260 KB Output is correct
16 Correct 484 ms 45160 KB Output is correct
17 Correct 401 ms 49840 KB Output is correct
18 Correct 459 ms 48688 KB Output is correct
19 Correct 199 ms 44388 KB Output is correct
20 Correct 182 ms 45716 KB Output is correct
21 Correct 183 ms 45148 KB Output is correct
22 Correct 173 ms 45504 KB Output is correct
23 Correct 174 ms 45560 KB Output is correct
24 Correct 191 ms 44120 KB Output is correct
25 Correct 173 ms 45188 KB Output is correct
26 Correct 229 ms 43816 KB Output is correct
27 Correct 3 ms 5460 KB Output is correct
28 Correct 4 ms 5408 KB Output is correct
29 Correct 4 ms 5412 KB Output is correct
30 Correct 4 ms 5408 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct
32 Incorrect 4 ms 5460 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 5016 KB Output isn't correct
2 Halted 0 ms 0 KB -