oj.uz

Submission #551852

# Submission time Handle Problem Language Result Execution time Memory
551852 2022-04-21T18:14:18 Z nicolaalexandra Swapping Cities (APIO20_swap) C++14
6 / 100
 146 ms 53476 KB 
#include <bits/stdc++.h>
#include "swap.h"
#define DIM 200010
#define INF 2000000000
using namespace std;

struct muchie{
    int x,y,cost;
} mch[DIM];

vector<pair <int,int> > L[DIM];
vector <int> edg[DIM];
pair <int,int> rmq[20][DIM*3];
int t[DIM],ok[DIM],g[DIM],dp[DIM],p[DIM],level[DIM],E[DIM*3],first[DIM],g2[DIM];
int n,m,subtask,maxi,k;

inline int cmp (muchie a, muchie b){
    return a.cost < b.cost;
}

inline int get_rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}

void dfs (int nod, int tata){

    E[++k] = nod;
    first[nod] = k;
    level[nod] = 1 + level[tata];
    for (auto vecin : edg[nod]){
        if (vecin != tata){
            dfs (vecin,nod);
            E[++k] = nod;
        }
    }

}

inline int get_lca (int x, int y){
    int posx = first[x], posy = first[y];
    if (posx > posy)
        swap (posx,posy);
    int nr = p[posy-posx+1];
    pair <int,int> sol = min (rmq[nr][posx], rmq[nr][posy-(1<<nr)+1]);
    return E[sol.second];
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {

    int i,j,rad;

    n = N, m = M;
    for (i=0;i<m;i++){
        int x = U[i], y = V[i], cost = W[i];
        x++, y++;

        L[x].push_back(make_pair(y,cost));
        L[y].push_back(make_pair(x,cost));
        maxi = max (maxi,cost);

        mch[i+1] = {x,y,cost};
    }

    subtask = 1;
    for (i=1;i<=n;i++)
        if (L[i].size() > 2)
            subtask = 0;

    sort (mch+1,mch+m+1,cmp);

    for (i=1;i<=n;i++){
        t[i] = dp[i] = -1;
        ok[i] = g[i] = g2[i] = 0;
        //a[i].push_back(i);
    }

    /// ok[i] - cand devine ok componenta cu radacina in i
    for (i=1;i<=m;i++){

        int x = mch[i].x, y = mch[i].y;
        int radx = get_rad(x), rady = get_rad(y);

        if (radx != rady){
            if (t[radx] > t[rady])
                swap (radx, rady);

            //if (!ok[radx] && ok[rady])
             //   ok[radx] = i;


           // if (ok[radx] && !ok[rady])
               // ok[rady] = i;


            edg[radx].push_back(rady); /// arborele unirilor
            g2[rady]++;

            t[radx] += t[rady];
            t[rady] = radx;

            g[x]++, g[y]++;
            if (g[x] >= 3 || g[y] >= 3){
                if (!ok[radx])
                    ok[radx] = i;
            }
        } else {
            /// o sa am un ciclu in componenta asta

            if (!ok[radx])
                ok[radx] = i;
        }
    }

    for (i=1;i<=n;i++)
        if (!g2[i])
            rad = i;

    dfs (rad,0);

    for (i=1;i<=k;i++)
        rmq[0][i] = make_pair(level[E[i]],i);

    for (i=1;(1<<i)<=k;i++)
        for (j=1;j<=k;j++){
            rmq[i][j] = rmq[i-1][j];
            if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<(i-1))].first < rmq[i][j].first)
                rmq[i][j] = rmq[i-1][j + (1<<(i-1))];
        }

    for (i=2;i<=k;i++)
        p[i] = p[i/2] + 1;
}


int getMinimumFuelCapacity(int X, int Y) {

    if (subtask == 1){
        if (m == n-1)
            return -1;
        else return maxi;
    }

    X++, Y++;

    int lca = get_lca (X,Y);

    int aux = X, maxim = 0;
    while (aux != lca){
        maxim = max (maxim,mch[ok[aux]].cost);
        aux = t[aux];
    }

    aux = Y;
    while (aux != lca){
        maxim = max (maxim,mch[ok[aux]].cost);
        aux = t[aux];
    }

    while (!ok[lca] && lca)
        lca = t[lca];

    maxim = max (maxim,mch[ok[lca]].cost);

    if (!maxim)
        return -1;
    else return maxim;


}
/*
int main (){

    FILE *fin = fopen ("date.in", "r");
    FILE *fout = fopen ("date.out", "w");

    int N, M;
    assert(2 == fscanf(fin, "%d %d", &N, &M));

    std::vector<int> U(M), V(M), W(M);
    for (int i = 0; i < M; ++i) {
        assert(3 == fscanf(fin, "%d %d %d", &U[i], &V[i], &W[i]));
    }

    int Q;
    assert(1 == fscanf(fin,"%d", &Q));

    std::vector<int> X(Q), Y(Q);
    for (int i = 0; i < Q; ++i) {
        assert(2 == fscanf(fin,"%d %d", &X[i], &Y[i]));
    }

    init(N, M, U, V, W);

    std::vector<int> minimum_fuel_capacities(Q);
    for (int i = 0; i < Q; ++i) {
        minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
    }

    for (int i = 0; i < Q; ++i) {
        fprintf(fout, "%d\n", minimum_fuel_capacities[i]);
    }



    return 0;
}

*/

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:120:9: warning: 'rad' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |     dfs (rad,0);
      |     ~~~~^~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9696 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 6 ms 10068 KB Output is correct
6 Correct 6 ms 10068 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 67 ms 41548 KB Output is correct
10 Correct 92 ms 48788 KB Output is correct
11 Correct 89 ms 48084 KB Output is correct
12 Correct 93 ms 50264 KB Output is correct
13 Correct 78 ms 49544 KB Output is correct
14 Correct 72 ms 41728 KB Output is correct
15 Correct 138 ms 50964 KB Output is correct
16 Correct 134 ms 49788 KB Output is correct
17 Correct 135 ms 52148 KB Output is correct
18 Correct 146 ms 51376 KB Output is correct
19 Correct 64 ms 19012 KB Output is correct
20 Correct 130 ms 52232 KB Output is correct
21 Correct 140 ms 50776 KB Output is correct
22 Correct 142 ms 53476 KB Output is correct
23 Correct 126 ms 52736 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9696 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 135 ms 50612 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9696 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 6 ms 10068 KB Output is correct
6 Correct 6 ms 10068 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Incorrect 5 ms 9684 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9696 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9940 KB Output is correct
5 Correct 6 ms 10068 KB Output is correct
6 Correct 6 ms 10068 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 6 ms 10068 KB Output is correct
9 Correct 67 ms 41548 KB Output is correct
10 Correct 92 ms 48788 KB Output is correct
11 Correct 89 ms 48084 KB Output is correct
12 Correct 93 ms 50264 KB Output is correct
13 Correct 78 ms 49544 KB Output is correct
14 Correct 72 ms 41728 KB Output is correct
15 Correct 138 ms 50964 KB Output is correct
16 Correct 134 ms 49788 KB Output is correct
17 Correct 135 ms 52148 KB Output is correct
18 Correct 146 ms 51376 KB Output is correct
19 Incorrect 135 ms 50612 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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