제출 #880752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
880752		niter	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	90 ms	225876 KiB

dango_maker

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define ff first
#define ss second
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define entr cerr << endl;
#define spac cerr << ' ';
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x <<  " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) x.begin(), x.end()
#define unilize(x) x.resize(unique(BAE(x)) - x.begin())
#define unisort(x) sort(BAE(x)); unilize(x);
#define bye exit(0);
using namespace std;
typedef long long ll;

const int mxn = 3010;
const int INF = (int)(1e7);
const int nINF = -(int)(1e7);
char c[mxn][mxn];
vector<pii> EV;
const int mxN = (int)(9e6) + 3000;
bool vis[mxN], can[mxN];
vector<int> E[mxN];
int p[mxn][mxn];

int dfs(int st){
    if(E[st].empty()) return 1;
    vector<int> v[2], dp[3];
    v[0].pb(st);
    vis[st] = true;
    v[1].pb(-1);
    int dir = 0, tmp_dir = 0;
    int two_son, three_son, only_son, son_cnt;
    for(int ind = 0; ; ind++){
//        opa(ind) op(dir)
//        STL(v[0])
//        STL(v[1])
        if(v[0][ind] != -1 && v[1][ind] == -1) dir = 0;
        else if(v[0][ind] == -1 && v[1][ind] != -1) dir = 1;
        else if(v[0][ind] == -1 && v[1][ind] == -1) break;
        v[0].pb(-1);
        v[1].pb(-1);
        tmp_dir = dir;
        loop(j,0,2){
            son_cnt = 0;
            for(auto &i:E[v[tmp_dir][ind]]){
                if(!vis[i]){
                    only_son = i;
                    son_cnt++;
                    vis[i] = true;
                    if(E[i].size() == 2){
                        two_son = i;
                    }
                    else if(E[i].size() == 3){
                        three_son = i;
                    }
                }
            }
            if(son_cnt == 1){
                v[tmp_dir][ind+1] = only_son;
            }
            else if(son_cnt == 2){
                v[tmp_dir][ind+1] = three_son;
                v[!tmp_dir][ind] = two_son;
            }

            tmp_dir = !tmp_dir;
            if(v[tmp_dir][ind] == -1){
                break;
            }
        }
    }
    int ret = 0;
    int m = v[0].size() - 1;
    dp[0].resize(m);
    dp[1].resize(m);
    dp[2].resize(m);
    dp[0][0] = 0;                           // not take
    dp[1][0] = (v[0][0] == -1) ? nINF : 1;  // take upper
    dp[2][0] = (v[1][0] == -1) ? nINF : 1;  // take lower
    loop(i,1,m){
        dp[0][i] = max(max(dp[0][i-1], dp[1][i-1]), dp[2][i-1]);
        dp[1][i] = max(dp[2][i-1], dp[0][i-1]) + 1;
        dp[2][i] = max(dp[1][i-1], dp[0][i-1]) + 1;
        if(v[0][i] == -1) dp[1][i] = nINF;
        if(v[1][i] == -1) dp[2][i] = nINF;
        ret = max(dp[0][i], max(dp[1][i], dp[2][i]));
    }
    return ret;
}

void check(int x, int y, int ind){
    if(p[x][y] == 0){
        p[x][y] = ind;
    }
    else{
        EV.pb({p[x][y], ind});
    }
}

int main(){
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
    loop(i,0,n){
        loop(j,0,m){
            cin >> c[i][j];
        }
    }
    int now = 0;
    loop(i,0,n){
        loop(j,0,m){
            if(c[i][j] == 'R' && c[i][j+1] == 'G' && c[i][j+2] == 'W'){
                now++;
                check(i, j, now);
                check(i, j + 1, now);
                check(i, j + 2, now);
                can[now] = true;
            }
            if(c[i][j] == 'R' && c[i+1][j] == 'G' && c[i+2][j] == 'W'){
                now++;
                check(i, j, now);
                check(i + 1, j, now);
                check(i + 2, j, now);
                can[now] = true;
            }
        }
    }
    unisort(EV);
    for(auto &i:EV){
        E[i.ff].pb(i.ss);
        E[i.ss].pb(i.ff);
//        opa(i.ff) op(i.ss);
    }
    int ans = 0;
    loop(i,1,now + 1){
        if((!vis[i]) && can[i]){
            int tmp = dfs(i);
            ans += tmp;
        }
    }
    cout << ans << '\n';
}

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

dango_maker.cpp: In function 'int dfs(int)':
dango_maker.cpp:69:35: warning: 'three_son' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |                 v[tmp_dir][ind+1] = three_son;
dango_maker.cpp:70:34: warning: 'two_son' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |                 v[!tmp_dir][ind] = two_son;

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