5194 2023. 04. 21 15:22:47 sztomi Városok cpp11 Hibás válasz 10/100 300ms 20632 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1896 KiB
2 Hibás válasz 3ms 2128 KiB
subtask2 10/10
3 Elfogadva 3ms 2344 KiB
4 Elfogadva 3ms 2420 KiB
5 Elfogadva 2ms 2508 KiB
6 Elfogadva 3ms 2640 KiB
subtask3 0/5
7 Időlimit túllépés 300ms 7276 KiB
8 Időlimit túllépés 252ms 4836 KiB
9 Időlimit túllépés 300ms 8796 KiB
10 Időlimit túllépés 275ms 10044 KiB
11 Időlimit túllépés 250ms 10884 KiB
subtask4 0/40
12 Hibás válasz 148ms 8880 KiB
13 Időlimit túllépés 268ms 11508 KiB
14 Időlimit túllépés 268ms 12212 KiB
15 Időlimit túllépés 277ms 12688 KiB
16 Elfogadva 187ms 11048 KiB
17 Időlimit túllépés 268ms 13572 KiB
18 Időlimit túllépés 244ms 13888 KiB
19 Időlimit túllépés 272ms 12332 KiB
20 Időlimit túllépés 263ms 13768 KiB
21 Elfogadva 30ms 17664 KiB
subtask5 0/45
22 Időlimit túllépés 264ms 15964 KiB
23 Időlimit túllépés 268ms 16988 KiB
24 Időlimit túllépés 259ms 17244 KiB
25 Időlimit túllépés 268ms 18108 KiB
26 Időlimit túllépés 247ms 19408 KiB
27 Időlimit túllépés 259ms 20632 KiB