Submission #1014064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014064		Otalp	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	287 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 = 5000000;
int dq[3010][3010];
int a[3021][3021];
int kto[MAXLS];
int bd[MAXLS];
int cnt[3];
int pos[MAXLS];
vector<int> q[MAXLS];
vector<int> ord;
int fup[MAXLS], tin[MAXLS], timer = 1;
int dp[MAXLS][2];
 
void dfs1(int v, int p = -1){
    pos[v] = 1;
    ord.pb(v);
    int cnt = 0;
    fup[v] = tin[v] = timer++;
    int dcnt = 0;
    for(int to: q[v]){
        if(to == p){
            continue;
        }
        if(pos[to]){
            fup[v] = min(fup[v],tin[to]);
        }
        else{
            dfs1(to, v);
            fup[v] = min(fup[v], fup[to]);
            if(fup[to] > tin[v]){
                bd[v] ++;
                bd[to] ++;
            }
            cnt++;
        }
    }
}

vector<int> dord;
int bdcnt = 0;
void dfs2(int v){
    pos[v] = 1;
    bdcnt ++;
    //cout<<v<<' '<<bd[v]<<'\n';
    for(int to: q[v]){
        if(!bd[to] and bd[v] == 2) dord.pb(to);
        if(pos[to] or !bd[to]) continue;
        dfs2(to);
    }
}

void dfs3(int v){
    pos[v] = 1;
    dp[v][0] = 0;
    dp[v][1] = 1;
    for(int to: q[v]){
        if(pos[to] or bd[to]) continue;
        dfs3(to);
        dp[v][1] += dp[to][0];
        dp[v][0] += dp[to][1];
    }
    dp[v][1] = max(dp[v][1], dp[v][0]);
}
 
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'){
                //cout<<i<<' '<<j<<' '<<ls+1<<" h\n";
                ls ++;
                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'){
                //cout<<i<<' '<<j<<' '<<ls+1<<" v\n";
                ls ++;
                add(i, j, ls);
                add(i-1, j, ls);
                add(i-2, j, ls);
                kto[ls] = 2;
            }
        }
    }
    if(ls > MAXLS) cout<<1/0;
    //cout<<ls<<'\n';
    for(int i=1; i<=ls; i++){
        //bd[i] = 1;
        //cout<<i<<'\n';
        //for(int v: q[i]) cout<<v<<' ';
        //for(int v: q[i]) if(i < v) cout<<i<<' '<<v<<'\n';
        //cout<<'\n';
    }
    ll ans = 0;
    //cout<<ls<<'\n';
    for(int i=1; i<=ls; i++){
        if(pos[i]) continue;
        ord.clear();
        dfs1(i);
        for(int v: ord){
            pos[v] = 0;
            if(bd[v] != q[v].size() and bd[v] != 0) bd[v] = 2;
            else if(bd[v] != q[v].size()) bd[v] = 1;
            else bd[v] = 0;
        }
        int cntb = 0;
        //cout<<cntb<<'\n';
        for(int v:ord){
            if(bd[v] and !pos[v]){
                dord.clear();
                bdcnt = 0;
                dfs2(v);
                //cout<<bdcnt<<'\n';
                //for(int u: dord) cout<<u<<'\n';
                if(dord.size() > 1 and ((bdcnt / 2 % 2 == 0 and kto[dord[0]] != kto[dord[1]] or
                                (bdcnt / 2 % 2 == 1 and kto[dord[0]] != kto[dord[1]])))){
                    q[dord[0]].pb(dord[1]);
                    q[dord[1]].pb(dord[0]);
                    //cout<<"ASDASD";
                }
            }
        }
        for(int v: ord){
            //cout<<v<<' '<<bd[v]<<'\n';
            if(bd[v]) cntb++;
        }
        ans += cntb / 2;
        //cout<<'\n';
        for(int v: ord){
            if(pos[v] or bd[v]) continue;
            cnt[1] = cnt[2] = 0;
            dfs3(v);
            ans += max(dp[v][1], dp[v][0]);
            //cout<<v<<' '<<max(cnt[1], cnt[2])<<'\n';
        }
    }
    cout<<ans<<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL);
    solve();
}

Compilation message (stderr)

dango_maker.cpp: In function 'void dfs1(int, int)':
dango_maker.cpp:28:9: warning: unused variable 'dcnt' [-Wunused-variable]
   28 |     int dcnt = 0;
      |         ^~~~
dango_maker.cpp: In function 'void solve()':
dango_maker.cpp:113:27: warning: division by zero [-Wdiv-by-zero]
  113 |     if(ls > MAXLS) cout<<1/0;
      |                          ~^~
dango_maker.cpp:130:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             if(bd[v] != q[v].size() and bd[v] != 0) bd[v] = 2;
      |                ~~~~~~^~~~~~~~~~~~~~
dango_maker.cpp:131:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |             else if(bd[v] != q[v].size()) bd[v] = 1;
      |                     ~~~~~~^~~~~~~~~~~~~~
dango_maker.cpp:143:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  143 |                 if(dord.size() > 1 and ((bdcnt / 2 % 2 == 0 and kto[dord[0]] != kto[dord[1]] or
      |                                          ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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