Cod sursa(job #3362074)

Utilizator SkibidiCezarCezar Bolba SkibidiCezar Data 2 august 2026 01:26:00
Problema Adapost Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.63 kb
#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;
ifstream fin ("adapost.in");
ofstream fout ("adapost.out");
int n, sink;
float st, mij, dist, maxflux, cost, iuli;
pair <float, float> sld[405], adp[405];
struct much{
    int a, b, c, f, per;
    float z;
};
vector <much> a;
vector <int> v[805];
int last[805];
float d[805], dvechi[805], reald[805];
int cuplaj[805];
bool mrc[405];

bool say_gex(int nod, float dist){ //say gex pt ca fac cupluri de noduri si atunci nodurile fac say gex lol
    // si eu cu cezar bolba
    // dar el e tsundere
    //sunt taken bro sybau
    // de mine bro
    //ba nu de tudor vianu huzz
    // nu mai suntem prieteni
    //oricum suntem frati nu ai unde sa pleci
    // ok you have a point
    if(mrc[nod]) return 0;
    mrc[nod] = 1;
    for(int i = 0; i < v[nod].size(); i++){
        if(a[v[nod][i]].c == 1 && a[v[nod][i]].z <= dist &&
           (!cuplaj[a[v[nod][i]].b] || say_gex(cuplaj[a[v[nod][i]].b], dist))){
            cuplaj[nod] = a[v[nod][i]].b;
            cuplaj[a[v[nod][i]].b] = nod;
            return 1;
        }
    }
    return 0;
}
//scuzati cearta de mai sus

int fa_cuplaj(float dist){
    int rez = 0;
    bool continua = 1;
    for(int i = 1; i <= n; i++){
        cuplaj[i] = 0;
        cuplaj[n+i] = 0;
    }
    while(continua){
        continua = 0;
        for(int i = 1; i <= n; i++){
            mrc[i] = 0;
        }
        for(int i = 1; i <= n; i++){
            if(!cuplaj[i] && say_gex(i, dist)){
                continua = 1;
                rez++;
            }
        }
    }
    return rez;
}

void omul_cu_clopot_vad(){
    for(int i = 0; i <= sink; i++){
        reald[i] = INT_MAX;
    }
    reald[0] = 0;
    for(int i = 0; i < a.size(); i++){
        if(reald[a[i].a] != INT_MAX){
            reald[a[i].b] = min(reald[a[i].b], reald[a[i].a] + a[i].z);
        }
    }
}

void deschistra(){
    for(int i = 0; i <= sink; i++){
        last[i] = -1;
        dvechi[i] = reald[i];
        d[i] = INT_MAX;
    }
    priority_queue <pair<float,int>, vector<pair<float,int>>, greater<pair<float,int>>> q;
    last[0] = -2;
    reald[0] = 0;
    d[0] = 0;
    q.push({0, 0});
    int nod;
    float dnou;
    much nxt;
    while(!q.empty()){
        nod = q.top().s;
        dnou = q.top().f;
        q.pop();
        if(dnou != d[nod]){
            continue;
        }
        for(int i = 0; i < v[nod].size(); i++){
            nxt = a[v[nod][i]];
            if(dnou + nxt.z + dvechi[nxt.a] - dvechi[nxt.b] < d[nxt.b] &&
               nxt.f < nxt.c){
                last[nxt.b] = v[nod][i];
                d[nxt.b] = dnou + nxt.z + dvechi[nxt.a] - dvechi[nxt.b];
                reald[nxt.b] = reald[nod] + nxt.z;
                q.push({d[nxt.b], nxt.b});
            }
        }
    }
}

void fa_un_drum(){
    int nod = sink, minim_ude = INT_MAX;
    while(last[nod] != -2){
        minim_ude = min(minim_ude, a[last[nod]].c - a[last[nod]].f);
        nod = a[last[nod]].a;
    }
    maxflux += minim_ude;
    cost += reald[sink] * minim_ude;
    nod = sink;
    while(last[nod] != -2){
        a[last[nod]].f += minim_ude;
        a[a[last[nod]].per].f -= minim_ude;
        nod = a[last[nod]].a;
    }
}

void flux(){
    int lastflux = -1;
    while(lastflux != maxflux){
        lastflux = maxflux;
        deschistra();
        if(last[sink] != -1){
            fa_un_drum();
        }
    }
}

int main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    fin >> n;
    sink = 2 * n + 1;
    for(int i = 1; i <= n; i++){
        fin >> sld[i].f >> sld[i].s;
    }
    for(int i = 1; i <= n; i++){
        fin >> adp[i].f >> adp[i].s;
        for(int j = 1; j <= n; j++){
            iuli = sqrt((adp[i].f - sld[j].f) * (adp[i].f - sld[j].f) +
                (adp[i].s - sld[j].s) * (adp[i].s - sld[j].s));
            a.push_back({j, n + i, 1, 0, 0, iuli});
        }
    }
    for(int i = 1; i <= n; i++){
        a.push_back({0, i, 1, 0, 0, 0});
        a.push_back({n + i, sink, 1, 0, 0, 0});
    }
    int m = a.size();
    for(int i = 0; i < m; i++){
        a.push_back({a[i].b, a[i].a, 0, 0, i, -a[i].z});
        a[i].per = i + m;
        v[a[i].a].push_back(i);
        v[a[i].b].push_back(i + m);
    }
    mij = (1 << 10);
    for(int i = 1; i <= 25; i++){
        if(fa_cuplaj(st + mij) == n){
            dist = st + mij;
        }
        else{
            st += mij;
        }
        mij /= 2;
    }
    fout << dist << " ";
    omul_cu_clopot_vad();
    //flux();
    fout << cost;
    return 0;
}