Cod sursa(job #3362485)

Utilizator SkibidiCezarCezar Bolba SkibidiCezar Data 9 august 2026 20:04:57
Problema Adapost Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.41 kb
#include <bits/stdc++.h>
#define f first
#define s second
#define float double

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

bool say_gex(int nod, long long 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 = n + 1; i < sink; i++){
        if(a[nod][i].z <= dist && (!cuplaj[i] || say_gex(cuplaj[i], dist))){
            cuplaj[nod] = i;
            cuplaj[i] = nod;
            return 1;
        }
    }
    return 0;
}
//scuzati cearta de mai sus

int fa_cuplaj(long long 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;
}

//Piesa the masque de la edge of sanity ar trebui sa fie una din cele 7 minuni
//A opta minune
//Oare stie domnul Dan Swano sa faca flux maxim de cost minim?

void omul_cu_clopot_vad(){
    for(int i = 0; i <= sink; i++){
        reald[i] = INT_MAX;
        mrc[i] = 0;
    }
    reald[0] = 0;
    queue <int> q;
    q.push(0);
    mrc[0] = 1;
    int nod, nxt;
    while(!q.empty()){
        nod = q.front();
        q.pop();
        for(int i = 0; i < v[nod].size(); i++){
            nxt = v[nod][i];
            if(reald[nod] + a[nod][nxt].z < reald[nxt]){
                reald[nxt] = reald[nod] + a[nod][nxt].z;
                if(!mrc[nxt]){
                    q.push(nxt);
                    mrc[nxt] = 1;
                }
            }
        }
        mrc[nod] = 0;
    }
}

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

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

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

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;
        a[0][i] = {1, 0, 0};
        v[0].push_back(i);
        v[i].push_back(0);
    }
    for(int i = 1; i <= n; i++){
        fin >> adp[i].f >> adp[i].s;
        for(int j = 1; j <= n; j++){
            morariu = 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));
            morariu *= 1000000;
            iuli = morariu;
            maxd = max(maxd, iuli);
            a[j][n+i] = {1, 0, iuli};
            a[n+i][j] = {0, 0, -iuli};
        }
        a[n+i][sink] = {1, 0, 0};
        v[n+i].push_back(sink);
        v[sink].push_back(n + i);
    }
    mij = 1;
    while(mij < maxd) mij *= 2;
    while(mij >= 1){
        //cout << st + mij << " ";
        if(fa_cuplaj(st + mij) == n){
            dist = st + mij;
        }
        else{
            st += mij;
        }
        mij /= 2;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(a[i][n+j].z <= dist){
                v[i].push_back(n + j);
                v[n+j].push_back(i);
            }
        }
    }
    flux();
    acc_dist = dist;
    acc_dist /= 1000000;
    acc_cost = cost;
    acc_cost /= 1000000;
    fout << acc_dist << " " << acc_cost;
    return 0;
}