51952023-04-21 15:24:03sztomiVárosokcpp11Hibás válasz 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz3ms1828 KiB
2Hibás válasz3ms2072 KiB
subtask20/10
3Hibás válasz2ms2144 KiB
4Hibás válasz3ms2276 KiB
5Hibás válasz2ms2316 KiB
6Hibás válasz3ms2544 KiB
subtask35/5
7Elfogadva78ms8764 KiB
8Elfogadva16ms4352 KiB
9Elfogadva78ms8888 KiB
10Elfogadva78ms9416 KiB
11Elfogadva76ms9104 KiB
subtask40/40
12Hibás válasz8ms3880 KiB
13Hibás válasz74ms9436 KiB
14Hibás válasz72ms9568 KiB
15Elfogadva72ms9880 KiB
16Elfogadva9ms4360 KiB
17Hibás válasz74ms10056 KiB
18Hibás válasz67ms9016 KiB
19Hibás válasz26ms5952 KiB
20Hibás válasz48ms8108 KiB
21Hibás válasz25ms9732 KiB
subtask50/45
22Hibás válasz78ms10252 KiB
23Hibás válasz78ms9948 KiB
24Hibás válasz63ms9036 KiB
25Hibás válasz63ms8988 KiB
26Hibás válasz78ms10188 KiB
27Hibás válasz79ms10672 KiB