This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define MAX 150000
lli n,t,a,b,act,k,num;
map<pair<lli,lli>, lli> mapa;
vector<lli> hijos[MAX+2];
lli dir[16] = {-1,0,1,0,-1,1,1,-1,0,1,0,-1,1,1,-1,-1};
lli visitados[MAX+2],dis[MAX+2];
queue<lli> cola;
vector<lli> res;
void dfs(lli pos) {
res.push_back(pos);
for(auto h : hijos[pos]) {
if (dis[h] <= dis[pos]) continue;
dfs(h);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> t;
rep(i,1,n) {
cin >> a >> b;
mapa[{a,b}] = i;
rep(o,0,7) {
if (mapa.find({a+dir[o],b + dir[o+8]}) != mapa.end()) {
k = mapa[{a+dir[o],b + dir[o+8]}];
hijos[k].push_back(i);
hijos[i].push_back(k);
}
}
}
//correcto
cola.push(1);
visitados[1] = 1;
num = 0;
while (!cola.empty()) {
act = cola.front();
cola.pop();
num++;
for(auto h : hijos[act]) {
if (visitados[h] == 1) continue;
visitados[h] = 1;
dis[h] = dis[act] + 1;
cola.push(h);
}
}
if (num < n) {
cout << "NO";
return 0;
}
dfs(1);
cout << "YES\n";
for (auto r : res) cout << r << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |