제출 #880742

#제출 시각아이디문제언어결과실행 시간메모리
880742niterDango Maker (JOI18_dango_maker)C++14
13 / 100
90 ms216160 KiB
#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(); dp[0].resize(m); dp[1].resize(m); dp[2].resize(m); dp[0][0] = 0; // not take dp[0][1] = (v[0][0] != -1); // take upper dp[0][2] = (v[0][1] != -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])); } // STL(v[0]) // STL(v[1]) 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;
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...