#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define ll long long
#define ll long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
//mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "parks.h"
// static void check(bool cond, string message) {
// if (!cond) {
// printf("%s\n", message.c_str());
// fclose(stdout);
// exit(0);
// }
// }
// static int n;
// static bool build_called;
// static int m;
// static vector<int> _u, _v, _a, _b;
// void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
// check(!build_called, "build is called more than once");
// build_called = true;
// m = u.size();
// check(int(v.size()) == m, "u.size() != v.size()");
// check(int(a.size()) == m, "u.size() != a.size()");
// check(int(b.size()) == m, "u.size() != b.size()");
// check(m <= 2*n, "Construction too large"); // Vertex degrees are at most 4
// _u = u;
// _v = v;
// _a = a;
// _b = b;
// }
// for DSU to check in the end
map < pair < int , int > , int > pos ;
int ss[ N ] , pp[ N ] ;
void create( int node ){
pp[ node ] = node ;
ss[ node ] = 1 ;
return ;
}
int find( int node ){
if( pp[ node ] == node ) return node ;
return pp[ node ] = find( pp[ node ] ) ;
}
void unite( int a , int b ){
a = find( a ) ; b = find( b ) ;
if( a == b ) return ;
if( ss[ a ] < ss[ b ] ) swap( a , b ) ;
if( ss[ a ] == ss[ b ] ) ss[ a ] ++ ;
pp[ b ] = a ;
return ;
}
// done DSU UPP
vector < int > x[ N ] ;
map < pair < int , int > , int > fn , dak ;
int construct_roads( vector<int> X, vector<int> Y){
int n = X.size() ;
FOR( i , n ){
x[ X[ i ] ].pb( Y[ i ] ) ;
fn[ { X[ i ] , Y[ i ] } ] = i ;
pos[ { X[ i ] , Y[ i ] } ] = i ;
create( i ) ;
}
// if( ( x[ 2 ].size() + x[ 4 ].size() ) == n )
sort( x[ 2 ].begin() , x[ 2 ].end() ) ;
sort( x[ 4 ].begin() , x[ 4 ].end() ) ;
vector < int > u , v , a , b ;
FOR( i , x[ 2 ].size() ){
if( i != x[ 2 ].size() - 1 ){
if( x[ 2 ][ i + 1 ] - x[ 2 ][ i ] == 2 ){
u.pb( pos[ { 2 , x[ 2 ][ i ] } ] ) ;
v.pb( pos[ { 2 , x[ 2 ][ i + 1 ] } ] ) ;
a.pb( 1 ) ;
b.pb( x[ 2 ][ i ] + 1 ) ;
unite( pos[ { 2 , x[ 2 ][ i ] } ] , pos[ { 2 , x[ 2 ][ i + 1 ] } ] ) ;
}
}
}
// now the important stuff
int tt = 0 ;
int A = 0 , B = 0 ;
FOR( i , x[ 4 ].size() ){
if( i != x[ 4 ].size() - 1 ){
if( x[ 4 ][ i + 1 ] - x[ 4 ][ i ] == 2 ){
u.pb( pos[ { 4 , x[ 4 ][ i ] } ] ) ;
v.pb( pos[ { 4 , x[ 4 ][ i + 1 ] } ] ) ;
if( dak.find( { 5 , x[ 4 ][ i ] + 1 } ) == dak.end() ){
a.pb( 5 ) ;
b.pb( x[ 4 ][ i ] + 1 ) ;
dak[ { 5 , x[ 4 ][ i ] + 1 } ] = 1 ;
}
else{
if( dak.find({ 3 , x[ 4 ][ i ] + 1 } ) != dak.end() ) tt = -1 ;
a.pb( 3 ) ;
b.pb( x[ 4 ][ i ] + 1 ) ;
dak[ { 3 , x[ 4 ][ i ] + 1 } ] = 1 ;
}
unite( pos[ { 4 , x[ 4 ][ i ] } ] , pos[ { 4 , x[ 4 ][ i + 1 ] } ] ) ;
}
}
if( A == 0 || ( i != 0 && x[ 4 ][ i ] - x[ 4 ][ i - 1 ] != 2 ) ){
if( fn.find( { 2 , x[ 4 ][ i ] } ) == fn.end() ){
A = 0 ;
}
else{
int ot = fn[ { 2 , x[ 4 ][ i ] } ] ;
u.pb( ot ) ;
v.pb( pos[ { 4 , x[ 4 ][ i ] } ] ) ;
a.pb( 3 ) ;
if( dak.find( { 3 , x[ 4 ][ i ] - 1 } ) == dak.end() ){
b.pb( x[ 4 ][ i ] - 1 ) ; dak[ { 3 , x[ 4 ][ i ] - 1 } ] = 1 ; }
else{
if( dak.find({ 3 , x[ 4 ][ i ] + 1 } ) != dak.end() ) tt = -1 ;
b.pb( x[ 4 ][ i ] + 1 ) ; dak[ { 3 , x[ 4 ][ i ] + 1 } ] = 1 ;
}
unite( ot , pos[ { 4 , x[ 4 ][ i ] } ] ) ;
A = 1 ;
}
} else A = 0 ;
if( B == 0 || ( i != 0 && x[ 4 ][ i ] - x[ 4 ][ i - 1 ] != 2 ) ){
if( fn.find( { 6 , x[ 4 ][ i ] } ) == fn.end() ){
B = 0 ;
}
else{
int ot = fn[ { 6 , x[ 4 ][ i ] } ] ;
u.pb( ot ) ;
v.pb( pos[ { 4 , x[ 4 ][ i ] } ] ) ;
a.pb( 5 ) ;
if( dak.find( { 5 , x[ 4 ][ i ] - 1 } ) == dak.end() ){
b.pb( x[ 4 ][ i ] - 1 ) ; dak[ { 5 , x[ 4 ][ i ] - 1 } ] = 1 ; }
else{
if( dak.find({ 5 , x[ 4 ][ i ] + 1 } ) != dak.end() ) tt = -1 ;
b.pb( x[ 4 ][ i ] + 1 ) ; dak[ { 5 , x[ 4 ][ i ] + 1 } ] = 1 ;
}
unite( ot , pos[ { 4 , x[ 4 ][ i ] } ] ) ;
B = 1 ;
}
} else B = 0 ;
}
FOR( i , x[ 6 ].size() ){
if( i != x[ 6 ].size() - 1 ){
if( x[ 6 ][ i + 1 ] - x[ 6 ][ i ] == 2 ){
u.pb( pos[ { 6 , x[ 6 ][ i ] } ] ) ;
v.pb( pos[ { 6 , x[ 6 ][ i + 1 ] } ] ) ;
a.pb( 7 ) ;
b.pb( x[ 6 ][ i ] + 1 ) ;
unite( pos[ { 6 , x[ 6 ][ i ] } ] , pos[ { 6 , x[ 6 ][ i + 1 ] } ] ) ;
}
}
}
if( tt == -1 ) return 0 ;
int tt = find( 0 ) ;
int tit = 0 ;
FOR( i , n ) if( find( i ) != tt ) tit = -1 ;
if( tit == -1 ) return 0 ;
build( u , v , a , b ) ;
return 1 ;
}
// int main() {
// assert(scanf("%d", &n) == 1);
// vector<int> x(n), y(n);
// for (int i = 0; i < n; i++) {
// assert(scanf("%d%d", &x[i], &y[i]) == 2);
// }
// fclose(stdin);
// build_called = false;
// const int possible = construct_roads(x, y);
// check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
// if (possible == 1) {
// check(build_called, "construct_roads() returned 1 without calling build()");
// } else {
// check(!build_called, "construct_roads() called build() but returned 0");
// }
// printf("OK\n");
// printf("%d\n", possible);
// if (possible == 1) {
// printf("%d\n", m);
// for (int j = 0; j < m; j++) {
// printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
// }
// }
// fclose(stdout);
// return 0;
// }
Compilation message
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:13:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
103 | FOR( i , x[ 2 ].size() ){
| ~~~~~~~~~~~~~~~~~
parks.cpp:103:5: note: in expansion of macro 'FOR'
103 | FOR( i , x[ 2 ].size() ){
| ^~~
parks.cpp:104:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | if( i != x[ 2 ].size() - 1 ){
| ~~^~~~~~~~~~~~~~~~~~~~
parks.cpp:13:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
117 | FOR( i , x[ 4 ].size() ){
| ~~~~~~~~~~~~~~~~~
parks.cpp:117:5: note: in expansion of macro 'FOR'
117 | FOR( i , x[ 4 ].size() ){
| ^~~
parks.cpp:119:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | if( i != x[ 4 ].size() - 1 ){
| ~~^~~~~~~~~~~~~~~~~~~~
parks.cpp:13:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
180 | FOR( i , x[ 6 ].size() ){
| ~~~~~~~~~~~~~~~~~
parks.cpp:180:5: note: in expansion of macro 'FOR'
180 | FOR( i , x[ 6 ].size() ){
| ^~~
parks.cpp:181:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | if( i != x[ 6 ].size() - 1 ){
| ~~^~~~~~~~~~~~~~~~~~~~
parks.cpp:192:9: error: redeclaration of 'int tt'
192 | int tt = find( 0 ) ;
| ^~
parks.cpp:115:5: note: 'int tt' previously declared here
115 | int tt = 0 ;
| ^~
