Submission #812812

#	Time	Username	Problem	Language	Result	Execution time	Memory
812812		lollipop	Fountain Parks (IOI21_parks)	C++17	15 / 100	434 ms	61504 KiB

parks

#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 ;
   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 (stderr)

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 ){
      |           ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30