1312 2022. 05. 07 17:07:56 FulopMate Útépítés cpp14 Elfogadva 100/100 537ms 7564 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 3860 KiB
2 Elfogadva 0/0 8ms 6488 KiB
3 Elfogadva 5/5 2ms 3876 KiB
4 Elfogadva 5/5 2ms 3876 KiB
5 Elfogadva 5/5 2ms 4012 KiB
6 Elfogadva 5/5 2ms 4044 KiB
7 Elfogadva 5/5 2ms 4028 KiB
8 Elfogadva 5/5 2ms 4036 KiB
9 Elfogadva 5/5 2ms 4048 KiB
10 Elfogadva 5/5 2ms 4052 KiB
11 Elfogadva 5/5 3ms 4136 KiB
12 Elfogadva 5/5 2ms 4124 KiB
13 Elfogadva 5/5 3ms 4152 KiB
14 Elfogadva 5/5 3ms 4300 KiB
15 Elfogadva 5/5 4ms 4832 KiB
16 Elfogadva 5/5 59ms 7460 KiB
17 Elfogadva 5/5 537ms 7564 KiB
18 Elfogadva 5/5 8ms 6000 KiB
19 Elfogadva 5/5 9ms 6048 KiB
20 Elfogadva 5/5 10ms 7124 KiB
21 Elfogadva 5/5 10ms 7228 KiB
22 Elfogadva 5/5 6ms 6016 KiB