#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int construct_roads(vector<int> x, vector<int> y) {
int n = sz(x);
vector<pair<pii,int>> p(n);
vector<int> u_ans, v_ans, a_ans, b_ans;
map<pii, int> ind;
for(int i = 0; i < n; i++)
p[i] = {{x[i], y[i]},i}, ind[{x[i], y[i]}] = i;
sort(all(p));
vector<vector<pii>> v(7);
queue<pii> inter[7];
for(int i = 0; i < n; i++)
v[p[i].fr.fr].pb({p[i].fr.sc, p[i].sc});
for(int i = 0, last = -1; i < sz(v[2]); i++) {
if(last == -1) last = v[2][i].fr;
if(i+1 == sz(v[2]) or v[2][i+1].fr - v[2][i].fr != 2) {
inter[2].push({last, v[2][i].fr});
last = -1;
continue;
}
u_ans.pb(v[2][i].sc);
v_ans.pb(v[2][i+1].sc);
a_ans.pb(1);
b_ans.pb(v[2][i].fr + 1);
}
for(int i = 0, last = -1; i < sz(v[6]); i++) {
if(i+1 == sz(v[6]) or v[6][i+1].fr - v[6][i].fr != 2) {
inter[6].push({last, v[6][i].fr});
last = -1;
continue;
}
u_ans.pb(v[6][i].sc);
v_ans.pb(v[6][i+1].sc);
a_ans.pb(7);
b_ans.pb(v[6][i].fr + 1);
}
vector<pii> to_add_1, to_add_2;
set<pii> used; // a e b
bool ok2 = 0, ok6 = 0;
for(int i = 0, last = -1; i < sz(v[4]); i++) {
int pos = v[4][i].fr;
if(last == -1) last = pos;
if(sz(inter[2]) and inter[2].front().sc < pos and ok2) inter[2].pop(), ok2 = 0;
if(sz(inter[2]) and inter[2].front().fr <= pos and pos <= inter[2].front().sc) {
if(last <= pos-2 and inter[2].front().fr <= pos-2) continue;
u_ans.pb(v[4][i].sc);
v_ans.pb(ind[{2,pos}]);
a_ans.pb({3});
b_ans.pb({pos-1});
used.insert({3, pos-1});
ok2 = 1;
}
if(sz(inter[6]) and inter[6].front().sc < pos and ok6) inter[6].pop(), ok6 = 0;
if(sz(inter[6]) and inter[6].front().fr <= pos and pos <= inter[6].front().sc) {
if(last <= pos-2 and inter[6].front().fr <= pos-2) continue;
to_add_2.pb({v[4][i].sc, ind[{6,pos}]});
ok6 = 1;
}
if(i+1 == sz(v[4]) or v[4][i+1].fr - v[4][i].fr != 2) last = -1;
else if(i+1 < sz(v[4])) to_add_1.pb({v[4][i].sc, v[4][i+1].sc});
}
for(auto [A,B] : to_add_1) {
if(used.count({3,y[A]+1})) {
u_ans.pb(A);
v_ans.pb(B);
a_ans.pb(5);
b_ans.pb(y[A]+1);
used.insert({5,y[A]+1});
}
else {
u_ans.pb(A);
v_ans.pb(B);
a_ans.pb(3);
b_ans.pb(y[A]+1);
}
}
for(auto [A,B] : to_add_2) {
if(used.count({5,y[A]-1})) {
u_ans.pb(A);
v_ans.pb(B);
a_ans.pb(5);
b_ans.pb(y[A]+1);
}
else {
u_ans.pb(A);
v_ans.pb(B);
a_ans.pb(5);
b_ans.pb(y[A]-1);
}
}
vector<int> edges[n];
for(int i = 0; i < sz(u_ans); i++)
edges[u_ans[i]].pb(v_ans[i]), edges[v_ans[i]].pb(u_ans[i]);
queue<int> fila;
vector<bool> vis;
fila.push(0);
vis[0] = 1;
while(!fila.empty()) {
int at = fila.front();
fila.pop();
for(int viz : edges[at])
if(!vis[viz]) fila.push(viz), vis[viz] = 1;
}
for(int i = 0; i < n; i++) if(!vis[i]) return 0;
build(u_ans, v_ans, a_ans, b_ans);
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
