51942023-04-21 15:22:47sztomiVárosokcpp11Hibás válasz 10/100300ms20632 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());
    // 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
1Elfogadva3ms1896 KiB
2Hibás válasz3ms2128 KiB
subtask210/10
3Elfogadva3ms2344 KiB
4Elfogadva3ms2420 KiB
5Elfogadva2ms2508 KiB
6Elfogadva3ms2640 KiB
subtask30/5
7Időlimit túllépés300ms7276 KiB
8Időlimit túllépés252ms4836 KiB
9Időlimit túllépés300ms8796 KiB
10Időlimit túllépés275ms10044 KiB
11Időlimit túllépés250ms10884 KiB
subtask40/40
12Hibás válasz148ms8880 KiB
13Időlimit túllépés268ms11508 KiB
14Időlimit túllépés268ms12212 KiB
15Időlimit túllépés277ms12688 KiB
16Elfogadva187ms11048 KiB
17Időlimit túllépés268ms13572 KiB
18Időlimit túllépés244ms13888 KiB
19Időlimit túllépés272ms12332 KiB
20Időlimit túllépés263ms13768 KiB
21Elfogadva30ms17664 KiB
subtask50/45
22Időlimit túllépés264ms15964 KiB
23Időlimit túllépés268ms16988 KiB
24Időlimit túllépés259ms17244 KiB
25Időlimit túllépés268ms18108 KiB
26Időlimit túllépés247ms19408 KiB
27Időlimit túllépés259ms20632 KiB