Submission #1007367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007367		Otalp	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	541 ms	262144 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define ll long long
#define pll pair<ll, ll>
#define pb push_back


const int MAXLS = 3000000;
int dq[3010][3010];
int a[3021][3021];
int kto[MAXLS];
int cnt[3];
int pos[MAXLS];
vector<int> q[MAXLS];
vector<int> ord;
int c[MAXLS];

void dfs(int v){
    pos[v] = 1;
    cnt[kto[v]] ++;
    ord.pb(v);
    for(int to: q[v]){
        if(pos[to]) continue;
        dfs(to);
    }
}

void add(int i, int j, int x){
    if(dq[i][j] != -1) q[dq[i][j]].pb(x), q[x].pb(dq[i][j]);
    dq[i][j] = x;
}


void solve(){   
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            cin>>c;
            a[i][j] = c;
            dq[i][j] = -1;
        }
    }
    int ls = 0;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(j >= 3 and a[i][j] == 'W' and a[i][j-1] == 'G' and a[i][j - 2] == 'R'){
                ls ++;
                //cout<<i<<' '<<j<<' '<<ls<<"v\n";
                add(i, j, ls);
                add(i, j-1, ls);
                add(i, j-2, ls);
                kto[ls] = 1;
            }
            if(i >= 3 and a[i][j] == 'W' and a[i-1][j] == 'G' and a[i-2][j] == 'R'){
                ls ++;
                //cout<<i<<' '<<j<<' '<<ls<<"h\n";
                add(i, j, ls);
                add(i-1, j, ls);
                add(i-2, j, ls);
                kto[ls] = 2;
            }
        }
    }
    ll ans = 0;
    //cout<<ls<<'\n';
    for(int i=1; i<=ls; i++){
        if(pos[i]) continue;
        cnt[1] = cnt[2] = 0;
        ord.clear();
        dfs(i);
        int res = 0;
        for(int k=0; k<(1 << ord.size()); k++){
            for(int i=0; i<ord.size(); i++){
                if((k&(1<<i))){
                    c[ord[i]] = 1;
                }
                else c[ord[i]] = 0;
            }
            int ok = 1;
            for(int v: ord){
                for(int to: q[v]){
                    if(c[to] and c[v]){
                        ok = 0;
                        break;
                    }
                }
            }
            if(ok){
                res = max(res, __builtin_popcount(k));
            }
        }
        ans += res;
        //cout<<res<<'\n';

    }
    cout<<ans<<'\n';
}

int main(){
    solve();
}

Compilation message (stderr)

dango_maker.cpp: In function 'void solve()':
dango_maker.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int i=0; i<ord.size(); i++){
      |                          ~^~~~~~~~~~~

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