52092023-04-22 12:31:54sztomiVárosokcpp11Accepted 100/10071ms23292 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";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Accepted3ms2168 KiB
subtask210/10
3Accepted2ms2112 KiB
4Accepted3ms2336 KiB
5Accepted3ms2372 KiB
6Accepted2ms2452 KiB
subtask35/5
7Accepted71ms9408 KiB
8Accepted16ms5432 KiB
9Accepted71ms10964 KiB
10Accepted71ms12356 KiB
11Accepted71ms13332 KiB
subtask440/40
12Accepted8ms8152 KiB
13Accepted67ms13756 KiB
14Accepted67ms14560 KiB
15Accepted65ms15048 KiB
16Accepted8ms10412 KiB
17Accepted68ms16060 KiB
18Accepted61ms16064 KiB
19Accepted25ms13072 KiB
20Accepted46ms15620 KiB
21Accepted20ms16248 KiB
subtask545/45
22Accepted71ms18192 KiB
23Accepted71ms19260 KiB
24Accepted57ms19332 KiB
25Accepted57ms20088 KiB
26Accepted70ms22188 KiB
27Accepted71ms23292 KiB