제출 #237593

#제출 시각아이디문제언어결과실행 시간메모리
237593HalfT-Covering (eJOI19_covering)C++14
10 / 100
37 ms792 KiB
#include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> #include <cmath> using namespace std; typedef vector<int> vi; typedef pair<int,int> pi; typedef long long ll; #define loop(i,a,b) for (int i = a; i <= b; i++) #define INF ((unsigned) ~0) #define F first #define S second #define PB push_back #define MP make_pair int m, n, k; ll res; int a[1000000]; map<pi, int> sp; int getA(int r, int c){ if(n * r + c >= 0 && n * r + c < m * n) return a[n * r + c]; return -1; } int& getAp(int r, int c){ if(n * r + c >= 0 && n * r + c < m * n) return a[n * r + c]; int x = -1; return x; } bool chkNgb(int r, int c){ if(n * r + c < 0 || n * r + c >= m * n) return true; if(sp.count(MP(r, c)) == 0) return true; if(sp[MP(r, c)] > 0) return true; int dn = 0; if(getA(r + 1, c) == -1) dn++; if(getA(r - 1, c) == -1) dn++; if(getA(r, c + 1) == -1) dn++; if(getA(r, c - 1) == -1) dn++; if(dn >= 2) return false; if(dn == 1){ res += max(getA(r + 1, c), 0); res += max(getA(r - 1, c), 0); res += max(getA(r, c + 1), 0); res += max(getA(r, c - 1), 0); getAp(r + 1, c) = -1; getAp(r - 1, c) = -1; getAp(r, c + 1) = -1; getAp(r, c - 1) = -1; sp[MP(r, c)] = 1; return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2); } if(sp.count(MP(r + 1, c + 1)) > 0){ res += max(getA(r + 1, c), 0); res += max(getA(r - 1, c), 0); res += max(getA(r, c - 1), 0); getAp(r + 1, c) = -1; getAp(r - 1, c) = -1; getAp(r, c - 1) = -1; sp[MP(r, c)] = 1; return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2); } if(sp.count(MP(r - 1, c + 1)) > 0){ res += max(getA(r + 1, c), 0); res += max(getA(r - 1, c), 0); res += max(getA(r, c - 1), 0); getAp(r + 1, c) = -1; getAp(r - 1, c) = -1; getAp(r, c - 1) = -1; sp[MP(r, c)] = 1; return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2); } if(sp.count(MP(r + 1, c - 1)) > 0){ res += max(getA(r + 1, c), 0); res += max(getA(r - 1, c), 0); res += max(getA(r, c + 1), 0); getAp(r + 1, c) = -1; getAp(r - 1, c) = -1; getAp(r, c + 1) = -1; sp[MP(r, c)] = 1; return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2); } if(sp.count(MP(r - 1, c - 1)) > 0){ res += max(getA(r + 1, c), 0); res += max(getA(r - 1, c), 0); res += max(getA(r, c + 1), 0); getAp(r + 1, c) = -1; getAp(r - 1, c) = -1; getAp(r, c + 1) = -1; sp[MP(r, c)] = 1; return chkNgb(r + 2, c) && chkNgb(r - 2, c) && chkNgb(r, c + 2) && chkNgb(r, c - 2); } return true; } pi dfs(int r, int c, int pr, int pc){ if(n * r + c < 0 || n * r + c >= m * n || sp.count(MP(r, c)) == 0) return MP(0, 1001); if(sp[MP(r, c)] == 2){ return MP(1, 1001); } sp[MP(r, c)] = 2; pi s = MP(0, 1001); for(int i = -1; i < 2; i += 2){ for(int j = -1; j < 2; j += 2){ if((r + i + j) != pr || (c + i - j) != pc){ res += max(getA(r + (i + j)/2, c + (i - j)/2), 0); //cout << r + (i + j)/2 << " " << c + (i - j)/2 << ":" << getA(r + (i + j)/2, c + (i - j)/2) << "\n"; s.S = min(s.S, getA(r + (i + j)/2, c + (i - j)/2)); pi p = dfs(r + i + j, c + i - j, r, c); s = MP(max(s.F, p.F), min(s.S, p.S)); getAp(r + (i + j)/2, c + (i - j)/2) = -1; } } } return s; } int main(){ res = 0; cin >> m >> n; for(int r = 0; r < m; r++) for(int c = 0; c < n; c++) cin >> a[n * r + c]; cin >> k; for(int i = 0; i < k; i++){ int r, c; cin >> r >> c; sp[MP(r, c)] = 0; res += a[n * r + c]; a[n * r + c] = -1; } for(map<pi, int>::iterator it = sp.begin(); it != sp.end(); it++){ if(!chkNgb((it->F).F, (it->F).S)){ cout << "No\n"; return 0; } } //cout << res << "\n"; for(map<pi, int>::iterator it = sp.begin(); it != sp.end(); it++){ int r = (it->F).F; int c = (it->F).S; //cout << sp[MP(r, c)] << "\n"; if(sp[MP(r, c)] == 0){ pi p = dfs(r, c, -1, -1); //cout << p.F << "\n"; if(p.F == 0) res -= p.S; } } cout << res << "\n"; }

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

covering.cpp: In function 'int& getAp(int, int)':
covering.cpp:36:9: warning: reference to local variable 'x' returned [-Wreturn-local-addr]
     int x = -1;
         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...