#include <bits/stdc++.h>
using namespace std;
int wx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, wy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
signed main(){
int n, t; cin >> n >> t;
vector<pair<int, int>> a(n);
vector<int> chk(n);
vector<int> ans;
for(int i = 0; i < n; ++i){
cin >> a[i].first >> a[i].second;
}
for(int rep = 0; rep < n; ++rep){
map<int, map<int, int>> mp;
for(int i = 0; i < n; ++i){
if(chk[i]) continue;
mp[a[i].first][a[i].second] = i + 1;
}
vector<vector<int>> way(n);
for(int i = 0; i < n; ++i){
if(chk[i]) continue;
for(int j = 0; j < 8; ++j){
int nx = a[i].first + wx[j], ny = a[i].second + wy[j];
if(mp[nx][ny]){
way[i].push_back(mp[nx][ny] - 1);
}
}
}
int mx = -1;
vector<int> in(n), mn(n), cnt(n);
int inN = 0;
auto dfs = [&](auto&&self, int x, int pr)->void{
in[x] = ++inN;
mn[x] = in[x];
for(auto&nxt:way[x]){
if(nxt == pr) continue;
if(in[nxt]){
mn[x] = min(mn[x], in[nxt]);
}
else{
self(self, nxt, x);
if(mn[nxt] >= in[x]){
++cnt[x];
}
mn[x] = min(mn[x], mn[nxt]);
}
}
};
int rt = -1;
for(int i = 0; i < n; ++i){
if(!chk[i]){
dfs(dfs, i, -1);
rt = i;
break;
}
}
for(int i = n - 1; i >= 0; --i){
if(chk[i]) continue;
if(!in[i]){
cout << "NO\n";
return 0;
}
}
for(int i = n - 1; i >= 0; --i){
if(chk[i]) continue;
if(!((i != rt && cnt[i]) || (i == rt && cnt[i] > 1))){
chk[i] = 1;
ans.push_back(i);
break;
}
}
}
if((int)ans.size() != n){
cout << "NO\n";
}
else{
cout << "YES\n";
reverse(ans.begin(), ans.end());
for(auto&i:ans){
cout << i + 1 << '\n';
}
}
return 0;
}
Compilation message
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:31:13: warning: unused variable 'mx' [-Wunused-variable]
31 | int mx = -1;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
212 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
212 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
212 KB |
ans=YES N=9 |
| 6 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
212 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
212 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
212 KB |
ans=YES N=10 |
| 10 |
Incorrect |
0 ms |
212 KB |
Added cell 8 (2,0) not reachable from infinity |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
212 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
212 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
212 KB |
ans=YES N=9 |
| 6 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
212 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
212 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
212 KB |
ans=YES N=10 |
| 10 |
Incorrect |
0 ms |
212 KB |
Added cell 8 (2,0) not reachable from infinity |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
212 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
212 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
212 KB |
ans=YES N=9 |
| 6 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
212 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
212 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
212 KB |
ans=YES N=10 |
| 10 |
Incorrect |
0 ms |
212 KB |
Added cell 8 (2,0) not reachable from infinity |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1748 KB |
ans=NO N=1934 |
| 2 |
Correct |
4 ms |
724 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
2246 ms |
616 KB |
Added cell 1824 (370,234) not reachable from infinity |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
ans=YES N=1 |
| 2 |
Correct |
1 ms |
212 KB |
ans=YES N=4 |
| 3 |
Correct |
0 ms |
212 KB |
ans=NO N=4 |
| 4 |
Correct |
1 ms |
212 KB |
ans=YES N=5 |
| 5 |
Correct |
0 ms |
212 KB |
ans=YES N=9 |
| 6 |
Correct |
0 ms |
212 KB |
ans=YES N=5 |
| 7 |
Correct |
0 ms |
212 KB |
ans=NO N=9 |
| 8 |
Correct |
0 ms |
212 KB |
ans=NO N=10 |
| 9 |
Correct |
0 ms |
212 KB |
ans=YES N=10 |
| 10 |
Incorrect |
0 ms |
212 KB |
Added cell 8 (2,0) not reachable from infinity |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
209 ms |
12860 KB |
ans=NO N=66151 |
| 2 |
Correct |
235 ms |
25324 KB |
ans=NO N=64333 |
| 3 |
Execution timed out |
3539 ms |
14224 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1748 KB |
ans=NO N=1934 |
| 2 |
Correct |
4 ms |
724 KB |
ans=NO N=1965 |
| 3 |
Incorrect |
2246 ms |
616 KB |
Added cell 1824 (370,234) not reachable from infinity |
| 4 |
Halted |
0 ms |
0 KB |
- |
