제출 #1014014

#제출 시각아이디문제언어결과실행 시간메모리
1014014OtalpDango Maker (JOI18_dango_maker)C++14
33 / 100
392 ms138836 KiB
#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 = 2000000;
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;
 
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;
    cnt[kto[v]] ++;
    for(int to: q[v]){
        if(pos[to] or bd[to]) continue;
        dfs3(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'){
                //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;
            }
        }
    }
    //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(cnt[1], cnt[2]);
            //cout<<v<<' '<<max(cnt[1], cnt[2])<<'\n';
        }
    }
    cout<<ans<<'\n';
}
 
int main(){
    solve();
}

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp: In function 'void dfs1(int, int)':
dango_maker.cpp:27:9: warning: unused variable 'dcnt' [-Wunused-variable]
   27 |     int dcnt = 0;
      |         ^~~~
dango_maker.cpp: In function 'void solve()':
dango_maker.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             if(bd[v] != q[v].size() and bd[v] != 0) bd[v] = 2;
      |                ~~~~~~^~~~~~~~~~~~~~
dango_maker.cpp:125:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             else if(bd[v] != q[v].size()) bd[v] = 1;
      |                     ~~~~~~^~~~~~~~~~~~~~
dango_maker.cpp:137:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  137 |                 if(dord.size() > 1 and ((bdcnt / 2 % 2 == 0 and kto[dord[0]] != kto[dord[1]] or
      |                                          ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...