5209 2023. 04. 22 12:31:54 sztomi Városok cpp11 Elfogadva 100/100 71ms 23292 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pont;

#define x first
#define y second


struct el{
    int tol, ig;

    int get_masik(int x){
        if(x == tol) return ig;
        return tol;
    }
};

vector<pont> pontok;
vector<el> elek;
vector<vector<int>> graf;
vector<int> volt;
vector<int> par;
int dfs_db = 0;

bool dfs(int akt){
    if(volt[akt] >= dfs_db) return false;
    //cout << "csekkol: " << akt << "\n";
    volt[akt] = dfs_db;
    for(int ind : graf[akt]){
        int kov = elek[ind].get_masik(akt);
        if(par[kov] == -1 || dfs(par[kov])){
            par[kov] = akt;
            return true;
        }
    }
    return false;
}

struct node{
    int kord;
    bool x;
};

void kiir_node(node &n){
    cout << "kord: " << n.kord << (n.x ? " X" : " Y") << " ";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, a, b;
    cin >> n >> a >> b;
    pontok.resize(n);
    map<int, int> x_fajtak;
    map<int, int> y_fajtak;
    vector<node> tipusok;
    int ind = 0;
    for(auto &p : pontok){
        cin >> p.x >> p.y;
        if(!x_fajtak.count(p.x)){
            graf.push_back(vector<int>());
            volt.push_back(0);
            par.push_back(-1);
            tipusok.push_back({p.x, true});
            x_fajtak[p.x] = ind++;
        }
        if(!y_fajtak.count(p.y)){
            graf.push_back(vector<int>());
            volt.push_back(0);
            par.push_back(-1);
            tipusok.push_back({p.y, false});
            y_fajtak[p.y] = ind++;
        }

        graf[x_fajtak[p.x]].push_back(elek.size());
        graf[y_fajtak[p.y]].push_back(elek.size());

        elek.push_back({x_fajtak[p.x], y_fajtak[p.y]});
    }

    for(int i = 0; i < ind; i++){
/*
        cout << "-------------\n";
        cout << "ind: " << i << "\n";
        kiir_node(tipusok[i]); cout << "\n";
        cout << "kapcsolatok: ";
        for(int temp : graf[i]){
            int kov = elek[temp].get_masik(i);
            kiir_node(tipusok[kov]); cout << ", ";
        }
        cout << "\n";
        cout << "-----------------\n";
*/
        if(tipusok[i].x){
            dfs_db++;
            dfs(i);
        }
    }

    int epit_db = 0;

    for(int i = 0; i < ind; i++){
        if(par[i] != -1){
            if(!tipusok[i].x) epit_db++;
            par[par[i]] = i;
        }
    }

    /*
    for(int i = 0; i < ind; i++){
        kiir_node(tipusok[i]);
        if(par[i] != -1){
            cout << " par:"; kiir_node(tipusok[par[i]]); cout << "\n";
        }
        else{
            cout << "nincs par\n";
        }
    }
    */

    for(auto e : elek){
        if(par[e.tol] == -1 || par[e.ig] == -1){
            //cout << "uj par: " << e.tol << " " << e.ig << "\n";
            par[e.tol] = e.ig;
            par[e.ig] = e.tol;
            epit_db++;
        }
    }


    long long ret = (long long)ind*b + (long long)epit_db*a;
    cout << ret << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 3ms 2168 KiB
subtask2 10/10
3 Elfogadva 2ms 2112 KiB
4 Elfogadva 3ms 2336 KiB
5 Elfogadva 3ms 2372 KiB
6 Elfogadva 2ms 2452 KiB
subtask3 5/5
7 Elfogadva 71ms 9408 KiB
8 Elfogadva 16ms 5432 KiB
9 Elfogadva 71ms 10964 KiB
10 Elfogadva 71ms 12356 KiB
11 Elfogadva 71ms 13332 KiB
subtask4 40/40
12 Elfogadva 8ms 8152 KiB
13 Elfogadva 67ms 13756 KiB
14 Elfogadva 67ms 14560 KiB
15 Elfogadva 65ms 15048 KiB
16 Elfogadva 8ms 10412 KiB
17 Elfogadva 68ms 16060 KiB
18 Elfogadva 61ms 16064 KiB
19 Elfogadva 25ms 13072 KiB
20 Elfogadva 46ms 15620 KiB
21 Elfogadva 20ms 16248 KiB
subtask5 45/45
22 Elfogadva 71ms 18192 KiB
23 Elfogadva 71ms 19260 KiB
24 Elfogadva 57ms 19332 KiB
25 Elfogadva 57ms 20088 KiB
26 Elfogadva 70ms 22188 KiB
27 Elfogadva 71ms 23292 KiB