51952023-04-21 15:24:03sztomiVárosokcpp11Wrong answer 5/10079ms10672 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pont;

#define x first
#define y second


vector<pont> pontok;
map<int, vector<int>> x_ugyanaz;
map<int, vector<int>> y_ugyanaz;
map<int, int> x_db;
map<int, int> y_db;

int javit_db(int akt){
    int x_d = x_db[pontok[akt].x];
    int y_d = y_db[pontok[akt].y];

    if(x_d != 0 && y_d != 0){
        return x_d + y_d;
    }
    else{
        return x_d + y_d;
    }
    return 0;
}

struct comp{
    bool operator()(int a, int b){
        int javit1 = javit_db(a);
        int javit2 = javit_db(b);

        if(javit1 == javit2){
            return a < b;
        }
        return javit1 > javit2;
    }
};


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

    int n, a, b;
    cin >> n >> a >> b;
    pontok.resize(n);
    for(int i = 0; i < n; i++){
        cin >> pontok[i].x >> pontok[i].y;
        if(!x_ugyanaz.count(pontok[i].x)){
            x_ugyanaz.insert({pontok[i].x, vector<int>()});
        }
        if(!y_ugyanaz.count(pontok[i].y)){
            y_ugyanaz.insert({pontok[i].y, vector<int>()});
        }
        x_ugyanaz[pontok[i].x].push_back(i);
        y_ugyanaz[pontok[i].y].push_back(i);
        x_db[pontok[i].x]++;
        y_db[pontok[i].y]++;
    }

    long long ret = (long long)b*(x_ugyanaz.size() + y_ugyanaz.size());

    cout << ret << "\n";
    return 0;
    // moho ?
    // mindig a legtobbet javitot csinaljuk meg
    set<int, comp> aktiv;

    for(int i = 0; i < n; i++){
        if(x_db[pontok[i].x] == 1 || y_db[pontok[i].y] == 1){
            x_db[pontok[i].x] = 0;
            y_db[pontok[i].y] = 0;
            ret += a;
            continue;
        }
        aktiv.insert(i);
    }

    int akt;
    while(!aktiv.empty()){
        akt = *aktiv.begin();
        aktiv.erase(aktiv.begin());
        int javit = javit_db(akt);
        //cout << "akt: " << akt << " hely: (" << pontok[akt].x << "; " << pontok[akt].y << ") javit: " << javit << "\n";
        if(javit == 0) continue;


        ret += a;

        for(int ind : x_ugyanaz[pontok[akt].x]){
            if(ind == akt) continue;
            aktiv.erase(ind);
        }
        x_db[pontok[akt].x] = 0;
        for(int ind : x_ugyanaz[pontok[akt].x]){
            if(ind == akt) continue;
            aktiv.insert(ind);
        }

        for(int ind : y_ugyanaz[pontok[akt].y]){
            if(ind == akt) continue;
            aktiv.erase(ind);
        }
        y_db[pontok[akt].y] = 0;
        for(int ind : y_ugyanaz[pontok[akt].y]){
            if(ind == akt) continue;
            aktiv.insert(ind);
        }
    }

    cout << ret << "\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer3ms1828 KiB
2Wrong answer3ms2072 KiB
subtask20/10
3Wrong answer2ms2144 KiB
4Wrong answer3ms2276 KiB
5Wrong answer2ms2316 KiB
6Wrong answer3ms2544 KiB
subtask35/5
7Accepted78ms8764 KiB
8Accepted16ms4352 KiB
9Accepted78ms8888 KiB
10Accepted78ms9416 KiB
11Accepted76ms9104 KiB
subtask40/40
12Wrong answer8ms3880 KiB
13Wrong answer74ms9436 KiB
14Wrong answer72ms9568 KiB
15Accepted72ms9880 KiB
16Accepted9ms4360 KiB
17Wrong answer74ms10056 KiB
18Wrong answer67ms9016 KiB
19Wrong answer26ms5952 KiB
20Wrong answer48ms8108 KiB
21Wrong answer25ms9732 KiB
subtask50/45
22Wrong answer78ms10252 KiB
23Wrong answer78ms9948 KiB
24Wrong answer63ms9036 KiB
25Wrong answer63ms8988 KiB
26Wrong answer78ms10188 KiB
27Wrong answer79ms10672 KiB