Submission #551825

#	Time	Username	Problem	Language	Result	Execution time	Memory
551825		nicolaalexandra	Swapping Cities (APIO20_swap)	C++14	13 / 100	189 ms	29508 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> a[DIM];
int t[DIM],ok[DIM],g[DIM],dp[DIM];
int n,m,subtask,maxi;

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 init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {

    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] = 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();

            //ok[radx] |= ok[rady];
            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;
    }


}


int getMinimumFuelCapacity(int X, int Y) {

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

    X++, Y++;

    if (dp[X] == -1 || dp[Y] == -1)
        return -1;
    else return max (dp[X],dp[Y]);
}
/*
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;
}

*/

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27