#include "parks.h"
#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
struct point{
ll x,y,id;
point(ll x1 = 0,ll y1 = 0,ll id1 = 0):x(x1),y(y1),id(id1){}
bool operator < (const point &p)const {
return MP(x,y) < MP(p.x,p.y);
}
};
const ll MAXN = 2e5+100;
ll dsu[MAXN];
ll f(ll x){
if (dsu[x] < 0)return x;
return (dsu[x] = f(dsu[x]));
}
bool join(ll x,ll y){
x = f(x),y = f(y);
if (x==y)return 0;
dsu[x] += dsu[y];
dsu[y] = x;
return 1;
}
struct road{
pll a,b;
ll id;
};
namespace scc{
vector <pair <pll,bool> > query;
void add_or(ll x,ll y,bool neg = 0){
// cout<<x<<' '<<y<<'\n';
query.push_back(MP(MP(x,y),neg));
}
vector <vector <ll> > g1,g2;
vector <bool> in;
void add(ll x,ll y){
g1[x].push_back(y);
g2[y].push_back(x);
}
void dfs(vector <vector <ll> > &adj,ll u,vector <ll> &order){
in[u] = 1;
for (auto v:adj[u]){
if (!in[v]){
dfs(adj,v,order);
}
}
order.push_back(u);
}
bool solve(vector <bool> &res){
ll n=sz(res)*2;
g1.resize(n);
g2.resize(n);
for (auto x:query){
if (x.se){
add(x.fi.fi<<1,x.fi.se<<1|1);
add(x.fi.se<<1,x.fi.fi<<1|1);
}
else{
add(x.fi.fi<<1|1,x.fi.se<<1);
add(x.fi.se<<1|1,x.fi.fi<<1);
}
}
vector <ll> order;
in = vector <bool> (n,0);
vector <ll> c(n);
for (ll i = 0;i < n;i ++){
if (!in[i]){
dfs(g1,i,order);
}
}
in = vector <bool> (n,0);
reverse(order.begin(),order.end());
ll ptr = 0;
for (auto x:order){
if (!in[x]) {
vector <ll> comp;
dfs(g2,x,comp);
for (auto x:comp)c[x] = ptr;
ptr++;
}
}
for (ll i = 0;i < sz(res);i ++){
if (c[i<<1]==c[i<<1|1])return 0;
res[i] = c[i<<1] > c[i<<1|1];
// cout<<res[i]<<' ';
}
// cout<<'\n';
return 1;
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
ll n = sz(x);
vector <point> a(n);
for (ll i = 0;i < n;i ++){
dsu[i] = -1;
a[i] = {x[i],y[i],i};
}
sort(a.begin(),a.end());
auto id = [&](pll x){
auto tmp = lower_bound(a.begin(),a.end(),point(x.fi,x.se,0));
if (tmp != a.end() && (*tmp).x==x.fi&&(*tmp).y==x.se)return (*tmp).id;
else return -1;
};
vector <road> all;
for (ll i = 0;i < n;i ++){
if (id(MP(a[i].x,a[i].y-2)) != -1) {
if (join(id(MP(a[i].x,a[i].y-2)),a[i].id)) {
all.push_back({MP(id(MP(a[i].x,a[i].y-2)),a[i].id),MP(a[i].x-1,a[i].y-1),sz(all)});
all.push_back({MP(id(MP(a[i].x,a[i].y-2)),a[i].id),MP(a[i].x+1,a[i].y-1),sz(all)});
scc::add_or(sz(all)-1,sz(all)-2);
}
}
if ((id(MP(a[i].x-2,a[i].y)) != -1)) {
if (join(id(MP(a[i].x-2,a[i].y)),a[i].id)) {
all.push_back({MP(id(MP(a[i].x-2,a[i].y)),a[i].id),MP(a[i].x-1,a[i].y+1),sz(all)});
all.push_back({MP(id(MP(a[i].x-2,a[i].y)),a[i].id),MP(a[i].x-1,a[i].y-1),sz(all)});
scc::add_or(sz(all)-1,sz(all)-2);
}
}
}
if (dsu[f(0)] != -n)return 0;
sort(all.begin(),all.end(),[](road a1,road a2){return a1.b < a2.b;});
for (ll i = 0;i + 1 < sz(all);i ++){
if (all[i].b == all[i+1].b){
// cout<<all[i].a.fi<<' '<<all[i].a.se<<' '<<all[i+1].a.fi<<' '<<all[i+1].a.se<<' '<<all[i].id<<' '<<all[i+1].id<<endl;
scc::add_or(all[i].id,all[i+1].id,1);
}
}
vector <bool> res(sz(all));
if (!scc::solve(res))return 0;
{
vector <ll> U,V,A,B;
for (ll i = 0;i < sz(all);i ++){
if (res[all[i].id]){
U.push_back(all[i].a.fi);
V.push_back(all[i].a.se);
A.push_back(all[i].b.fi);
B.push_back(all[i].b.se);
}
}
build(U, V, A, B);
return 1;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Edge between 0 and 1 appears more than once: appeared on positions 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Edge between 0 and 1 appears more than once: appeared on positions 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Edge between 0 and 1 appears more than once: appeared on positions 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Edge between 0 and 1 appears more than once: appeared on positions 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Edge between 0 and 1 appears more than once: appeared on positions 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Edge between 0 and 1 appears more than once: appeared on positions 0 and 1 |
| 3 |
Halted |
0 ms |
0 KB |
- |
