oj.uz

Submission #551872

# Submission time Handle Problem Language Result Execution time Memory
551872 2022-04-21T18:51:19 Z nicolaalexandra Swapping Cities (APIO20_swap) C++14
13 / 100
 150 ms 32964 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],a[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 (int 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 (int i=1;i<=n;i++)
        if (L[i].size() > 2)
            subtask = 0;

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

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

    for (int 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]){
                for (auto it : a[radx])
                    dp[it] = mch[i].cost;
                ok[radx] = i;
            }

            if (ok[radx] && !ok[rady]){
                for (auto it : a[rady])
                    dp[it] = mch[i].cost;
                ok[rady] = i;
            }

            for (auto it : a[rady])
                a[radx].push_back(it);
            a[rady].clear();


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

            g[x]++, g[y]++;
            if (g[x] >= 3 || g[y] >= 3){
                if (!ok[radx]){
                    ok[radx] = i;
                    for (auto it : a[radx])
                        dp[it] = mch[i].cost;
                }
            }
        } else {
            /// o sa am un ciclu in componenta asta

            if (!ok[radx]){
                ok[radx] = i;
                for (auto it : a[radx])
                    dp[it] = mch[i].cost;
            }
        }


        //if (get_rad(X) == get_rad(Y) && ok[get_rad(X)])
          //  return mch[i].cost;
    }

    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 maxim = max (dp[X],dp[Y]);

    int lca = get_lca(X,Y);
    maxim = max (maxim,mch[ok[lca]].cost);

    if (maxim <= 0)
        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:133:9: warning: 'rad' may be used uninitialized in this function [-Wmaybe-uninitialized]
  133 |     dfs (rad,0);
      |     ~~~~^~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14336 KB Output is correct
4 Correct 8 ms 14408 KB Output is correct
5 Correct 8 ms 14484 KB Output is correct
6 Correct 10 ms 14548 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 69 ms 26628 KB Output is correct
10 Correct 92 ms 29132 KB Output is correct
11 Correct 82 ms 28872 KB Output is correct
12 Correct 86 ms 29708 KB Output is correct
13 Correct 79 ms 27036 KB Output is correct
14 Correct 78 ms 26900 KB Output is correct
15 Correct 146 ms 31208 KB Output is correct
16 Correct 150 ms 30708 KB Output is correct
17 Correct 140 ms 31596 KB Output is correct
18 Correct 123 ms 28600 KB Output is correct
19 Correct 62 ms 20188 KB Output is correct
20 Correct 137 ms 32068 KB Output is correct
21 Correct 145 ms 32072 KB Output is correct
22 Correct 139 ms 32964 KB Output is correct
23 Correct 137 ms 30080 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 127 ms 30216 KB Output is correct
4 Correct 126 ms 30676 KB Output is correct
5 Correct 124 ms 30536 KB Output is correct
6 Correct 131 ms 30532 KB Output is correct
7 Correct 147 ms 30648 KB Output is correct
8 Correct 124 ms 30144 KB Output is correct
9 Correct 130 ms 30460 KB Output is correct
10 Correct 119 ms 30012 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14336 KB Output is correct
4 Correct 8 ms 14408 KB Output is correct
5 Correct 8 ms 14484 KB Output is correct
6 Correct 10 ms 14548 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 8 ms 14428 KB Output is correct
10 Incorrect 9 ms 14548 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14336 KB Output is correct
5 Correct 8 ms 14408 KB Output is correct
6 Correct 8 ms 14484 KB Output is correct
7 Correct 10 ms 14548 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 69 ms 26628 KB Output is correct
11 Correct 92 ms 29132 KB Output is correct
12 Correct 82 ms 28872 KB Output is correct
13 Correct 86 ms 29708 KB Output is correct
14 Correct 79 ms 27036 KB Output is correct
15 Incorrect 9 ms 14548 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14336 KB Output is correct
4 Correct 8 ms 14408 KB Output is correct
5 Correct 8 ms 14484 KB Output is correct
6 Correct 10 ms 14548 KB Output is correct
7 Correct 8 ms 14548 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 69 ms 26628 KB Output is correct
10 Correct 92 ms 29132 KB Output is correct
11 Correct 82 ms 28872 KB Output is correct
12 Correct 86 ms 29708 KB Output is correct
13 Correct 79 ms 27036 KB Output is correct
14 Correct 78 ms 26900 KB Output is correct
15 Correct 146 ms 31208 KB Output is correct
16 Correct 150 ms 30708 KB Output is correct
17 Correct 140 ms 31596 KB Output is correct
18 Correct 123 ms 28600 KB Output is correct
19 Correct 127 ms 30216 KB Output is correct
20 Correct 126 ms 30676 KB Output is correct
21 Correct 124 ms 30536 KB Output is correct
22 Correct 131 ms 30532 KB Output is correct
23 Correct 147 ms 30648 KB Output is correct
24 Correct 124 ms 30144 KB Output is correct
25 Correct 130 ms 30460 KB Output is correct
26 Correct 119 ms 30012 KB Output is correct
27 Incorrect 9 ms 14548 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 8 ms 14336 KB Output is correct
5 Correct 8 ms 14408 KB Output is correct
6 Correct 8 ms 14484 KB Output is correct
7 Correct 10 ms 14548 KB Output is correct
8 Correct 8 ms 14548 KB Output is correct
9 Correct 8 ms 14548 KB Output is correct
10 Correct 69 ms 26628 KB Output is correct
11 Correct 92 ms 29132 KB Output is correct
12 Correct 82 ms 28872 KB Output is correct
13 Correct 86 ms 29708 KB Output is correct
14 Correct 79 ms 27036 KB Output is correct
15 Correct 78 ms 26900 KB Output is correct
16 Correct 146 ms 31208 KB Output is correct
17 Correct 150 ms 30708 KB Output is correct
18 Correct 140 ms 31596 KB Output is correct
19 Correct 123 ms 28600 KB Output is correct
20 Correct 127 ms 30216 KB Output is correct
21 Correct 126 ms 30676 KB Output is correct
22 Correct 124 ms 30536 KB Output is correct
23 Correct 131 ms 30532 KB Output is correct
24 Correct 147 ms 30648 KB Output is correct
25 Correct 124 ms 30144 KB Output is correct
26 Correct 130 ms 30460 KB Output is correct
27 Correct 119 ms 30012 KB Output is correct
28 Incorrect 9 ms 14548 KB Output isn't correct
29 Halted 0 ms 0 KB -