Submission #1145359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145359		Robert_junior	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	112 ms	211828 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
const int N  = 9000100;
char a[3001][3001];
vector<pair<int, int>>g[N];
pair<int, int>mt[N];
int used[N], timer, n, m;
bool dfs(int v){
    if(used[v] == timer) return false;
    used[v] = timer;
    for(auto [to, to1]: g[v]){
        if(!mt[to].F && !mt[to1].F){
            mt[mt[v].F] = {0, 0};
            mt[mt[v].S] = {0, 0};
            mt[to] = {v, v};
            mt[to1] = {v, v};
            mt[v] = {to, to1};
            return true;
        }
    }
    for(auto [to, to1]: g[v]){
        if(!mt[to].F && mt[to1].F){
            if(dfs(mt[to1].F)){
                mt[mt[v].F] = {0, 0};
                mt[mt[v].S] = {0, 0};
                mt[to] = {v, v};
                mt[to1] = {v, v};
                mt[v] = {to, to1};
                return true;
            }
        }
        if(mt[to].F && !mt[to1].F){
            if(dfs(mt[to].F)){
                mt[mt[v].F] = {0, 0};
                mt[mt[v].S] = {0, 0};
                mt[to] = {v, v};
                mt[to1] = {v, v};
                mt[v] = {to, to1};
                return true;
            }
        }
    }
    for(auto [to, to1] : g[v]){
        if(dfs(mt[to].F) && dfs(mt[to1].F)){
            mt[mt[v].F] = {0, 0};
            mt[mt[v].S] = {0, 0};
            mt[to] = {v, v};
            mt[to1] = {v, v};
            mt[v] = {to, to1};
            return true;
        }
    }
    for(auto [to, to1]: g[v]){
        if(!mt[to].F && !mt[to1].F){
            mt[mt[v].F] = {0, 0};
            mt[mt[v].S] = {0, 0};
            mt[to] = {v, v};
            mt[to1] = {v, v};
            mt[v] = {to, to1};
            return true;
        }
    }
    for(auto [to, to1]: g[v]){
        if(!mt[to].F && mt[to1].F){
            if(dfs(mt[to1].F)){
                mt[mt[v].F] = {0, 0};
                mt[mt[v].S] = {0, 0};
                mt[to] = {v, v};
                mt[to1] = {v, v};
                mt[v] = {to, to1};
                return true;
            }
        }
        if(mt[to].F && !mt[to1].F){
            if(dfs(mt[to].F)){
                mt[mt[v].F] = {0, 0};
                mt[mt[v].S] = {0, 0};
                mt[to] = {v, v};
                mt[to1] = {v, v};
                mt[v] = {to, to1};
                return true;
            }
        }
    }
    for(auto [to, to1] : g[v]){
        if(dfs(mt[to].F) && dfs(mt[to1].F)){
            mt[mt[v].F] = {0, 0};
            mt[mt[v].S] = {0, 0};
            mt[to] = {v, v};
            mt[to1] = {v, v};
            mt[v] = {to, to1};
            return true;
        }
    }
    return false;
}
int func(int i, int j){
    return (i - 1) * m + j;
}
void solve(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin>>a[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i + 2 <= n){
                if(a[i][j] == 'R'&& a[i + 1][j] == 'G' && a[i + 2][j] == 'W'){
                    g[func(i, j)].pb({func(i + 1, j), func(i + 2, j)});
                }
            }
            if(j + 2 <= m){
                if(a[i][j] == 'R'&& a[i][j + 1] == 'G'&& a[i][j + 2] == 'W'){
                    g[func(i, j)].pb({func(i, j + 1), func(i, j + 2)});
                }
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n * m; i++){
        timer++;
        if(dfs(i)){
            ans++;
        }
    }
    cout<<ans;
}
signed main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67