제출 #259809

#제출 시각아이디문제언어결과실행 시간메모리
259809MarcoMeijerBuilding Skyscrapers (CEOI19_skyscrapers)C++14
61 / 100
3201 ms190712 KiB
#include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e9 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second #define sz size() // input template<class T> void IN(T& x) {cin >> x;} template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); } // output template<class T1, class T2> void OUT(const pair<T1,T2>& x); template<class T> void OUT(const T& x) {cout << x;} template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); } template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi," ",x.se);} template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); } //===================// // Added libraries // //===================// //===================// //end added libraries// //===================// void program(); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); program(); } //===================// // begin program // //===================// const int MX = 7e5; int dx4[]={-1,0,1,0}; int dy4[]={0,1,0,-1}; int dx8[]={ 0, 1, 1, 1, 0,-1,-1,-1}; int dy8[]={ 1, 1, 0,-1,-1,-1, 0, 1}; int n, t, m; int R[MX], C[MX]; bitset<MX> visited; map<ii,int> posID; map<ii,int> f; set<ii> build; set<ii> out; set<int> pq; vi ans; int outside; int p[MX], r[MX], sets; void buildDSU(int dsuSize) { RE(i,dsuSize) p[i]=i, r[i]=0; sets = dsuSize; } int getSet(int i) {return i==p[i]?i:p[i]=getSet(p[i]);} bool isSameSet(int i, int j) {return getSet(i)==getSet(j);} void unionSet(int i, int j) { if(!isSameSet(i,j)) { i=p[i], j=p[j]; sets--; if(r[i] > r[j]) { p[j] = i; } else { p[i] = j; if(r[i] == r[j]) r[j]++; } } } bool isEmpty(int i) { return isSameSet(i, outside); } bool hasEmptyConnected(ii p) { int x=p.fi, y=p.se; RE(d,4) { int nx=x+dx4[d]; int ny=y+dy4[d]; if(out.count({nx,ny})) return 1; } return 0; } bool canDestroy(ii p) { if(!hasEmptyConnected(p)) return 0; int x=p.fi, y=p.se; int start=0; bool isBuild[8]; RE(d,8) { int nx=x+dx8[d]; int ny=y+dy8[d]; isBuild[d] = build.count({nx,ny}); if(isBuild[d]) { start = d; } } RE(d,4) { int cd=d*2; int nd=(cd+2)%8; if(isBuild[cd] && isBuild[nd]) isBuild[(cd+1)%8]=1; } set<int> curRegions; bool last=1; int pos=(start+1)%8; while(pos!=start) { int nx=x+dx8[pos]; int ny=y+dy8[pos]; if(last && !isBuild[pos]) { int reg = getSet(posID[{nx,ny}]); if(curRegions.count(reg)) return 0; curRegions.insert(reg); } last = isBuild[pos]; pos=(pos+1)%8; } return 1; } void updateBuild(ii p) { if(canDestroy(p)) { pq.insert(f[p]); } else { pq.erase(f[p]); } } void addOutside(ii p) { if(out.count(p)) return; bool foundBuild=0; int x=p.fi, y=p.se; RE(d,8) { int nx=x+dx8[d]; int ny=y+dy8[d]; if(build.count({nx,ny})) { foundBuild=1; break; } } if(!foundBuild) return; out.insert(p); RE(d,4) { int nx=x+dx4[d]; int ny=y+dy4[d]; if(!build.count({nx,ny})) addOutside({nx,ny}); } RE(d,8) { int nx=x+dx8[d]; int ny=y+dy8[d]; if(build.count({nx,ny})) updateBuild({nx,ny}); } } void dfsPossible(ii p) { if(!build.count(p)) return; if(visited[f[p]]) return; visited[f[p]] = 1; int x=p.fi, y=p.se; RE(d,8) { int nx=x+dx8[d]; int ny=y+dy8[d]; dfsPossible({nx,ny}); } } bool isPossible() { visited.reset(); dfsPossible({R[1],C[1]}); RE1(i,n) if(!visited[i]) return 0; return 1; } void addPossible(ii p) { if(posID.count(p)) return; int res = posID.sz; posID[p] = res; } void program() { IN(n,t); RE1(i,n) IN(R[i],C[i]); RE1(i,n) build.insert({R[i],C[i]}); RE1(i,n) f[{R[i],C[i]}]=i; RE1(i,n) { int x=R[i], y=C[i]; RE(d,8) { int nx=x+dx8[d]; int ny=y+dy8[d]; addPossible({nx,ny}); } addPossible({x,y}); } m = posID.sz; // create dsu buildDSU(m); FOR(p,posID) { int x = p.fi.fi; int y = p.fi.se; if(build.count({x,y})) continue; RE(d,4) { int nx=x+dx4[d]; int ny=y+dy4[d]; if(build.count({nx,ny})) continue; if(!posID.count({nx,ny})) continue; unionSet(p.se, posID[{nx,ny}]); } } // set outside(if there is a solution) if(isPossible()) { ii start = *build.begin(); start.fi--; outside = posID[start]; addOutside(start); } // find solution while(!pq.empty()) { int p = *(--pq.end()); int x = R[p]; int y = C[p]; pq.erase(p); build.erase({x,y}); // update dsu RE(d,4) { int nx=x+dx4[d]; int ny=y+dy4[d]; if(build.count({nx,ny})) continue; if(!posID.count({nx,ny})) continue; unionSet(posID[{x,y}], posID[{nx,ny}]); } addOutside({R[p],C[p]}); ans.pb(p); } if(ans.sz == n) { OUTL("YES"); reverse(all(ans)); FOR(i,ans) OUTL(i); } else { OUTL("NO"); } }

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

skyscrapers.cpp: In function 'void program()':
skyscrapers.cpp:270:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(ans.sz == n) {
        ~~~~~~~^~~~
#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...