1313 2022. 05. 07 17:08:27 k_balint Útépítés cpp14 Elfogadva 100/100 542ms 7492 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 40401;

int n, m;
int N,tt;
vector<int> g[MAXN+1];
int par[MAXN+1];
int vis[MAXN+1];
bool A[MAXN+1];

bool novel(int v){
    if(vis[v]==tt) return 0;
    vis[v]=tt;

    for(int x:g[v]){
        if(par[x]==-1 || novel(par[x])){
            par[v]=x; par[x]=v;
            return 1;
        }
    }
    return 0;
}

int magyar(){
    tt=0; int cnt=0;
    for(int i=0;i<N;i++){
        par[i]=-1;
    }

    for(int i=0;i<N;i++){
        if(A[i] && par[i]==-1){
            ++tt;
            cnt+=novel(i);
        }
    }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m; N=(n+1)*(m+1);
    for(int i = 0; i < MAXN; i++){
        A[i]=i/(m+1)%2;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c; cin>>c;
            if(c == '/'){
                g[(i+1)*(m+1) + j].push_back(i*(m+1) + j+1);
                g[i*(m+1) + j+1].push_back((i+1)*(m+1) + j);
            }else if(c == '\\'){
                g[i*(m+1)+j].push_back((i+1)*(m+1)+j+1);
                g[(i+1)*(m+1)+j+1].push_back(i*(m+1)+j);
            }
        }
    }

    cout << magyar() << '\n';

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){

            if(par[i*(m+1)+j] == (i+1)*(m+1)+j+1){
                cout<<'\\';
            }

            else if(par[(i+1)*(m+1)+j] == i*(m+1)+j+1){
                cout<<'/';
            }

            else{
                cout << '.';
            }

        }
        cout << '\n';
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 3ms 3856 KiB
2 Elfogadva 0/0 9ms 6564 KiB
3 Elfogadva 5/5 2ms 3852 KiB
4 Elfogadva 5/5 2ms 3856 KiB
5 Elfogadva 5/5 2ms 3860 KiB
6 Elfogadva 5/5 2ms 4024 KiB
7 Elfogadva 5/5 2ms 3868 KiB
8 Elfogadva 5/5 2ms 4012 KiB
9 Elfogadva 5/5 2ms 4020 KiB
10 Elfogadva 5/5 2ms 4020 KiB
11 Elfogadva 5/5 3ms 4104 KiB
12 Elfogadva 5/5 3ms 4100 KiB
13 Elfogadva 5/5 3ms 4124 KiB
14 Elfogadva 5/5 4ms 4268 KiB
15 Elfogadva 5/5 4ms 4812 KiB
16 Elfogadva 5/5 61ms 7480 KiB
17 Elfogadva 5/5 542ms 7492 KiB
18 Elfogadva 5/5 8ms 5976 KiB
19 Elfogadva 5/5 9ms 6024 KiB
20 Elfogadva 5/5 12ms 7096 KiB
21 Elfogadva 5/5 12ms 7136 KiB
22 Elfogadva 5/5 6ms 5900 KiB