제출 #551852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551852		nicolaalexandra	자매 도시 (APIO20_swap)	C++14	6 / 100	146 ms	53476 KiB

swap

#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;
}

*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27