13122022-05-07 17:07:56FulopMateÚtépítéscpp14Accepted 100/100537ms7564 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';
    }
}
SubtaskSumTestVerdictTimeMemory
base100/100
1Accepted0/03ms3860 KiB
2Accepted0/08ms6488 KiB
3Accepted5/52ms3876 KiB
4Accepted5/52ms3876 KiB
5Accepted5/52ms4012 KiB
6Accepted5/52ms4044 KiB
7Accepted5/52ms4028 KiB
8Accepted5/52ms4036 KiB
9Accepted5/52ms4048 KiB
10Accepted5/52ms4052 KiB
11Accepted5/53ms4136 KiB
12Accepted5/52ms4124 KiB
13Accepted5/53ms4152 KiB
14Accepted5/53ms4300 KiB
15Accepted5/54ms4832 KiB
16Accepted5/559ms7460 KiB
17Accepted5/5537ms7564 KiB
18Accepted5/58ms6000 KiB
19Accepted5/59ms6048 KiB
20Accepted5/510ms7124 KiB
21Accepted5/510ms7228 KiB
22Accepted5/56ms6016 KiB