52272023-04-23 07:44:22sztomiMajomházcpp11Hibás válasz 0/100135ms32388 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz3ms1700 KiB
2Hibás válasz7ms3280 KiB
subtask20/10
3Hibás válasz3ms2088 KiB
4Hibás válasz3ms2308 KiB
5Hibás válasz3ms2532 KiB
6Hibás válasz2ms2612 KiB
7Hibás válasz3ms2740 KiB
subtask30/10
8Hibás válasz3ms3160 KiB
9Hibás válasz3ms3400 KiB
10Hibás válasz3ms3364 KiB
11Hibás válasz3ms3620 KiB
12Hibás válasz3ms3836 KiB
subtask40/20
13Hibás válasz7ms5152 KiB
14Hibás válasz7ms5144 KiB
15Hibás válasz7ms5108 KiB
16Hibás válasz7ms5212 KiB
17Hibás válasz7ms5504 KiB
18Hibás válasz7ms5688 KiB
subtask50/29
19Hibás válasz59ms18428 KiB
20Hibás válasz59ms18316 KiB
21Hibás válasz59ms18312 KiB
22Hibás válasz59ms18572 KiB
23Hibás válasz63ms18460 KiB
subtask60/31
24Hibás válasz128ms32192 KiB
25Hibás válasz127ms32188 KiB
26Hibás válasz127ms32188 KiB
27Hibás válasz127ms32204 KiB
28Hibás válasz128ms32176 KiB
29Hibás válasz128ms32280 KiB
30Hibás válasz127ms32200 KiB
31Hibás válasz134ms32172 KiB
32Hibás válasz130ms32168 KiB
33Hibás válasz129ms32176 KiB
34Hibás válasz134ms32172 KiB
35Hibás válasz129ms32300 KiB
36Hibás válasz135ms32280 KiB
37Hibás válasz129ms32276 KiB
38Hibás válasz134ms32388 KiB
39Hibás válasz128ms32280 KiB
40Hibás válasz135ms32272 KiB