제출 #1013996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013996		Otalp	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	11 ms	24152 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 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]){
                dcnt ++;
            }
            cnt++;
        }
    }
    if(q[v].size() - (p != -1 ?1 :0) != dcnt) bd[v] = 1;
    if(q[v].size() - (p != -1 ?1 :0) != dcnt and dcnt != 0) bd[v] = 2;
}

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;
            }
        }
    }
    for(int i=1; i<=ls; i++){
        //bd[i] = 1;
        //cout<<i<<'\n';
        //for(int v: q[i]) cout<<v<<' ';
        //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;
        }
        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:44:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     if(q[v].size() - (p != -1 ?1 :0) != dcnt) bd[v] = 1;
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
dango_maker.cpp:45:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |     if(q[v].size() - (p != -1 ?1 :0) != dcnt and dcnt != 0) bd[v] = 2;
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
dango_maker.cpp: In function 'void solve()':
dango_maker.cpp:133:61: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  133 |                 if(dord.size() > 1 and ((bdcnt / 2 % 2 == 0 and kto[dord[0]] != kto[dord[1]] or
      |                                          ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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