Submission #551789

#	Time	Username	Problem	Language	Result	Execution time	Memory
551789		nicolaalexandra	Swapping Cities (APIO20_swap)	C++14	0 / 100	2065 ms	19688 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];

priority_queue <pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > h;
vector<pair <int,int> > L[DIM];
deque <int> c;
int dist[DIM],t[DIM],cnt[DIM],f[DIM],viz[DIM],mrk[DIM];
int n,m,subtask,maxi;

void dijkstra (int start, int dist[], int cnt[], int t[]){

    for (int i=1;i<=n;i++){
        dist[i] = INF;
        cnt[i] = 0;
        t[i] = 0;
    }

    while (!h.empty())
        h.pop();

    dist[start] = 0;
    cnt[start] = 1;
    h.push(make_pair(dist[start],start));
    while (!h.empty()){
        int nod = h.top().second, cost = h.top().first;
        h.pop();
        if (dist[nod] != cost)
            continue;

        for (auto it : L[nod]){
            int vecin = it.first, cst = it.second;
            if (dist[nod] + cst < dist[vecin]){
                dist[vecin] = dist[nod] + cst;
                cnt[vecin] = cnt[nod];
                t[vecin] = nod;
                h.push(make_pair(dist[vecin],vecin));
            } else {
                if (dist[nod] + cst == dist[vecin])
                    cnt[vecin] += cnt[nod];
            }
        }
    }
}

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;

}

void dfs (int nod, int val){
    viz[nod] = 1;
    for (auto it : L[nod]){
        if (it.second > val || mrk[it.first] || viz[it.first])
            continue;
        dfs (it.first,val);
    }
}

inline int verif (int val, int x, int y){

    memset (viz,0,sizeof viz);
    memset (t,0,sizeof t);
    memset (mrk,0,sizeof mrk);

    c.clear();
    c.push_back(x);
    viz[x] = 1;

    int ok = 0;
    while (!c.empty()){
        int nod = c.front();
        c.pop_front();

        int cnt = 0;
        for (auto it : L[nod]){
            int vecin = it.first, cost = it.second;
            if (cost > val)
                continue;
            if (!viz[vecin]){
                viz[vecin] = 1 + viz[nod];
                t[vecin] = nod;
                c.push_back(vecin);
            }

            cnt++;
        }

        if (cnt > 2 && nod != x && nod != y)
            ok = 1;
    }

    if (!viz[y])
        return 0;

    if (ok)
        return 1;

    /// exista doua drumuri disjuncte intre x si y?
    int nod = y;
    while (nod){
        if (nod != y)
            mrk[nod] = 1;
        nod = t[nod];
    }

    memset (viz,0,sizeof viz);

    dfs (x,val);

    if (viz[y])
        return 1;

    return 0;
}

int getMinimumFuelCapacity(int x, int y) {

    if (subtask == 1)
        return -1;

    x++, y++;

    int st = 1, dr = maxi, sol = -1;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid,x,y)){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    return sol;


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