52272023-04-23 07:44:22sztomiMajomházcpp11Wrong answer 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";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer3ms1700 KiB
2Wrong answer7ms3280 KiB
subtask20/10
3Wrong answer3ms2088 KiB
4Wrong answer3ms2308 KiB
5Wrong answer3ms2532 KiB
6Wrong answer2ms2612 KiB
7Wrong answer3ms2740 KiB
subtask30/10
8Wrong answer3ms3160 KiB
9Wrong answer3ms3400 KiB
10Wrong answer3ms3364 KiB
11Wrong answer3ms3620 KiB
12Wrong answer3ms3836 KiB
subtask40/20
13Wrong answer7ms5152 KiB
14Wrong answer7ms5144 KiB
15Wrong answer7ms5108 KiB
16Wrong answer7ms5212 KiB
17Wrong answer7ms5504 KiB
18Wrong answer7ms5688 KiB
subtask50/29
19Wrong answer59ms18428 KiB
20Wrong answer59ms18316 KiB
21Wrong answer59ms18312 KiB
22Wrong answer59ms18572 KiB
23Wrong answer63ms18460 KiB
subtask60/31
24Wrong answer128ms32192 KiB
25Wrong answer127ms32188 KiB
26Wrong answer127ms32188 KiB
27Wrong answer127ms32204 KiB
28Wrong answer128ms32176 KiB
29Wrong answer128ms32280 KiB
30Wrong answer127ms32200 KiB
31Wrong answer134ms32172 KiB
32Wrong answer130ms32168 KiB
33Wrong answer129ms32176 KiB
34Wrong answer134ms32172 KiB
35Wrong answer129ms32300 KiB
36Wrong answer135ms32280 KiB
37Wrong answer129ms32276 KiB
38Wrong answer134ms32388 KiB
39Wrong answer128ms32280 KiB
40Wrong answer135ms32272 KiB