5195 2023. 04. 21 15:24:03 sztomi Városok cpp11 Hibás válasz 5/100 79ms 10672 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Hibás válasz 3ms 1828 KiB
2 Hibás válasz 3ms 2072 KiB
subtask2 0/10
3 Hibás válasz 2ms 2144 KiB
4 Hibás válasz 3ms 2276 KiB
5 Hibás válasz 2ms 2316 KiB
6 Hibás válasz 3ms 2544 KiB
subtask3 5/5
7 Elfogadva 78ms 8764 KiB
8 Elfogadva 16ms 4352 KiB
9 Elfogadva 78ms 8888 KiB
10 Elfogadva 78ms 9416 KiB
11 Elfogadva 76ms 9104 KiB
subtask4 0/40
12 Hibás válasz 8ms 3880 KiB
13 Hibás válasz 74ms 9436 KiB
14 Hibás válasz 72ms 9568 KiB
15 Elfogadva 72ms 9880 KiB
16 Elfogadva 9ms 4360 KiB
17 Hibás válasz 74ms 10056 KiB
18 Hibás válasz 67ms 9016 KiB
19 Hibás válasz 26ms 5952 KiB
20 Hibás válasz 48ms 8108 KiB
21 Hibás válasz 25ms 9732 KiB
subtask5 0/45
22 Hibás válasz 78ms 10252 KiB
23 Hibás válasz 78ms 9948 KiB
24 Hibás válasz 63ms 9036 KiB
25 Hibás válasz 63ms 8988 KiB
26 Hibás válasz 78ms 10188 KiB
27 Hibás válasz 79ms 10672 KiB