Submission #1007718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007718		Otalp	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	34 ms	66900 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 = 1000000;
    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, res1 = 0;
            if(true){
                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));
                    }
                }
            }
            
                cnt[1] = cnt[2] = 0;
                for(int v: ord) cnt[kto[v]] ++;
                res1 = max(kto[1], kto[2]);
            
     		if(res1 < res) cout<<1 / 0;
            ans += res;
            //cout<<res<<'\n';
     
        }
        cout<<ans<<'\n';
    }
     
    int main(){
        solve();
    }

Compilation message (stderr)

dango_maker.cpp: In function 'void solve()':
dango_maker.cpp:80:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                     for(int i=0; i<ord.size(); i++){
      |                                  ~^~~~~~~~~~~
dango_maker.cpp:105:31: warning: division by zero [-Wdiv-by-zero]
  105 |        if(res1 < res) cout<<1 / 0;
      |                             ~~^~~

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