51942023-04-21 15:22:47sztomiVárosokcpp11Wrong answer 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";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1896 KiB
2Wrong answer3ms2128 KiB
subtask210/10
3Accepted3ms2344 KiB
4Accepted3ms2420 KiB
5Accepted2ms2508 KiB
6Accepted3ms2640 KiB
subtask30/5
7Time limit exceeded300ms7276 KiB
8Time limit exceeded252ms4836 KiB
9Time limit exceeded300ms8796 KiB
10Time limit exceeded275ms10044 KiB
11Time limit exceeded250ms10884 KiB
subtask40/40
12Wrong answer148ms8880 KiB
13Time limit exceeded268ms11508 KiB
14Time limit exceeded268ms12212 KiB
15Time limit exceeded277ms12688 KiB
16Accepted187ms11048 KiB
17Time limit exceeded268ms13572 KiB
18Time limit exceeded244ms13888 KiB
19Time limit exceeded272ms12332 KiB
20Time limit exceeded263ms13768 KiB
21Accepted30ms17664 KiB
subtask50/45
22Time limit exceeded264ms15964 KiB
23Time limit exceeded268ms16988 KiB
24Time limit exceeded259ms17244 KiB
25Time limit exceeded268ms18108 KiB
26Time limit exceeded247ms19408 KiB
27Time limit exceeded259ms20632 KiB