5341 2023. 04. 26 07:48:27 sztomi Útépítés cpp11 Futási hiba 5/100 41ms 64860 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

#define sor first
#define oszlop second

const int MAXPONTDB = 201*201;

int n, m;
int pont_db;
vector<int> graf[MAXPONTDB];
bool volt[MAXPONTDB]{false};
bool szin[MAXPONTDB]{false};
int par[MAXPONTDB];

int hely_to_ind(pii p){
    return p.sor * (m+1) + p.oszlop;
}

pii ind_to_hely(int ind){
    return {ind / (m+1), ind % (m+1)};
}

void szinez(int akt, bool s=false){
    volt[akt] = true;
    szin[akt] = s;
    s = !s;
    for(int kov : graf[akt]){
        if(volt[kov]) continue;
        szinez(kov, s);
    }
}

bool par_keres(int akt){
    for(int kov : graf[akt]){
        if(par[kov] == -1 || par_keres(par[kov])){
            par[kov] = akt;
            return true;
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // maximal bipartite matching
    // sakktabla szinezes eseten egy el mindig azonos szinueket kot ossze
    cin >> n >> m;
    pont_db = (n+1) * (m+1);
    char c;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> c;
            if(c == '/'){
                int a = hely_to_ind({i+1, j});
                int b = hely_to_ind({i, j+1});
                graf[a].push_back(b);
                graf[b].push_back(a);
            }
            else if(c == '\\'){
                int a = hely_to_ind({i, j});
                int b = hely_to_ind({i+1, j+1});
                graf[a].push_back(b);
                graf[b].push_back(a);
            }
        }
    }


    for(int i = 0; i < pont_db; i++){
        if(!volt[i]) szinez(i);
    }

/*
    for(int i = 0; i < pont_db; i++){
        pii hely = ind_to_hely(i);
        cout << i << " (" << hely.first << ", " << hely.second << ") szin: " << szin[i] << ": ";
        for(int x : graf[i]){
            cout << x << ", ";
        }
        cout << "\n";
    }
*/

    fill(par, par+pont_db, -1);
    for(int i = 0;  i < pont_db; i++){
        if(szin[i] && par[i] == -1){
            par_keres(i);
        }
    }
/*
    for(int i = 0; i < pont_db; i++){
        cout << i << ": " << par[i] << "\n";
    }
*/
    int db = 0;
    vector<vector<char>> ki(n, vector<char>(m, '.'));
    for(int i = 0; i < pont_db; i++){
        if(par[i] != -1){
            db++;
            pii a = ind_to_hely(i);
            pii b = ind_to_hely(par[i]);
            pii hely = {min(a.sor, b.sor), min(a.oszlop, b.oszlop)};

            if(a == hely){
                ki[hely.sor][hely.oszlop] = '\\';
            }
            else{
                ki[hely.sor][hely.oszlop] = '/';
            }
        }
    }

    cout << db << "\n";
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cout << ki[i][j];
        }
        cout << "\n";
    }

}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 5/100
1 Elfogadva 0/0 4ms 3812 KiB
2 Futási hiba 0/0 34ms 64860 KiB
3 Futási hiba 0/5 29ms 64616 KiB
4 Futási hiba 0/5 32ms 64372 KiB
5 Futási hiba 0/5 29ms 64144 KiB
6 Futási hiba 0/5 29ms 63908 KiB
7 Futási hiba 0/5 32ms 63672 KiB
8 Futási hiba 0/5 29ms 63668 KiB
9 Futási hiba 0/5 32ms 63428 KiB
10 Futási hiba 0/5 37ms 63324 KiB
11 Futási hiba 0/5 35ms 63088 KiB
12 Futási hiba 0/5 32ms 63068 KiB
13 Futási hiba 0/5 32ms 63064 KiB
14 Futási hiba 0/5 32ms 63040 KiB
15 Futási hiba 0/5 29ms 63004 KiB
16 Futási hiba 0/5 34ms 62980 KiB
17 Futási hiba 0/5 39ms 62684 KiB
18 Elfogadva 5/5 9ms 9900 KiB
19 Futási hiba 0/5 37ms 62440 KiB
20 Futási hiba 0/5 34ms 62428 KiB
21 Futási hiba 0/5 41ms 62452 KiB
22 Futási hiba 0/5 37ms 62164 KiB