oj.uz

Submission #551869

# Submission time Handle Problem Language Result Execution time Memory
551869 2022-04-21T18:46:12 Z nicolaalexandra Swapping Cities (APIO20_swap) C++14
13 / 100
 152 ms 33092 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] = 1;
            }

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

            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] = 1;
                    for (auto it : a[radx])
                        dp[it] = mch[i].cost;
                }
            }
        } else {
            /// o sa am un ciclu in componenta asta

            if (!ok[radx]){
                ok[radx] = 1;
                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,dp[lca]);

    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:132:9: warning: 'rad' may be used uninitialized in this function [-Wmaybe-uninitialized]
  132 |     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 7 ms 14436 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 8 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 67 ms 26704 KB Output is correct
10 Correct 90 ms 29108 KB Output is correct
11 Correct 82 ms 28820 KB Output is correct
12 Correct 86 ms 29788 KB Output is correct
13 Correct 76 ms 27036 KB Output is correct
14 Correct 71 ms 26840 KB Output is correct
15 Correct 134 ms 31160 KB Output is correct
16 Correct 131 ms 30700 KB Output is correct
17 Correct 137 ms 31696 KB Output is correct
18 Correct 130 ms 28612 KB Output is correct
19 Correct 59 ms 20172 KB Output is correct
20 Correct 129 ms 32132 KB Output is correct
21 Correct 132 ms 32004 KB Output is correct
22 Correct 152 ms 33092 KB Output is correct
23 Correct 130 ms 30084 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 117 ms 30212 KB Output is correct
4 Correct 125 ms 30652 KB Output is correct
5 Correct 125 ms 30564 KB Output is correct
6 Correct 119 ms 30536 KB Output is correct
7 Correct 120 ms 30616 KB Output is correct
8 Correct 127 ms 30064 KB Output is correct
9 Correct 129 ms 30516 KB Output is correct
10 Correct 121 ms 30076 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 7 ms 14436 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 8 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 7 ms 14420 KB Output is correct
10 Incorrect 9 ms 14648 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14436 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 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 14548 KB Output is correct
10 Correct 67 ms 26704 KB Output is correct
11 Correct 90 ms 29108 KB Output is correct
12 Correct 82 ms 28820 KB Output is correct
13 Correct 86 ms 29788 KB Output is correct
14 Correct 76 ms 27036 KB Output is correct
15 Incorrect 9 ms 14648 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 7 ms 14436 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14548 KB Output is correct
6 Correct 8 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 67 ms 26704 KB Output is correct
10 Correct 90 ms 29108 KB Output is correct
11 Correct 82 ms 28820 KB Output is correct
12 Correct 86 ms 29788 KB Output is correct
13 Correct 76 ms 27036 KB Output is correct
14 Correct 71 ms 26840 KB Output is correct
15 Correct 134 ms 31160 KB Output is correct
16 Correct 131 ms 30700 KB Output is correct
17 Correct 137 ms 31696 KB Output is correct
18 Correct 130 ms 28612 KB Output is correct
19 Correct 117 ms 30212 KB Output is correct
20 Correct 125 ms 30652 KB Output is correct
21 Correct 125 ms 30564 KB Output is correct
22 Correct 119 ms 30536 KB Output is correct
23 Correct 120 ms 30616 KB Output is correct
24 Correct 127 ms 30064 KB Output is correct
25 Correct 129 ms 30516 KB Output is correct
26 Correct 121 ms 30076 KB Output is correct
27 Incorrect 9 ms 14648 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14420 KB Output is correct
4 Correct 7 ms 14436 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 8 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 14548 KB Output is correct
10 Correct 67 ms 26704 KB Output is correct
11 Correct 90 ms 29108 KB Output is correct
12 Correct 82 ms 28820 KB Output is correct
13 Correct 86 ms 29788 KB Output is correct
14 Correct 76 ms 27036 KB Output is correct
15 Correct 71 ms 26840 KB Output is correct
16 Correct 134 ms 31160 KB Output is correct
17 Correct 131 ms 30700 KB Output is correct
18 Correct 137 ms 31696 KB Output is correct
19 Correct 130 ms 28612 KB Output is correct
20 Correct 117 ms 30212 KB Output is correct
21 Correct 125 ms 30652 KB Output is correct
22 Correct 125 ms 30564 KB Output is correct
23 Correct 119 ms 30536 KB Output is correct
24 Correct 120 ms 30616 KB Output is correct
25 Correct 127 ms 30064 KB Output is correct
26 Correct 129 ms 30516 KB Output is correct
27 Correct 121 ms 30076 KB Output is correct
28 Incorrect 9 ms 14648 KB Output isn't correct
29 Halted 0 ms 0 KB -