Submission #799889

#TimeUsernameProblemLanguageResultExecution timeMemory
799889lollipopConnecting Supertrees (IOI20_supertrees)C++17
56 / 100
208 ms28028 KiB
#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 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 NN = 2e5 + 10 ; mt19937 R(time(0)); map < int , int > ma , ma1 ; #include "supertrees.h" // static int n; // static std::vector<std::vector<int>> p; // static std::vector<std::vector<int>> b; // static bool called = false; // static void check(bool cond, std::string message) { // if (!cond) { // printf("WA\n"); // printf("%s\n", message.c_str()); // fclose(stdout); // exit(0); // } // } // void build(std::vector<std::vector<int>> _b) { // check(!called, "build is called more than once"); // called = true; // check((int)_b.size() == n, "Invalid number of rows in b"); // for (int i = 0; i < n; i++) { // check((int)_b[i].size() == n, "Invalid number of columns in b"); // } // b = _b; // } int N ; vector< vector< int > > P , pas ; int pp[ NN ] , ss[ NN ] ; void create( int node ){ pp[ node ] = node ; ss[ node ] = 1 ; return ; } int find( int a ){ if( pp[ a ] == a ) return a ; return pp[ a ] = find( pp[ a ] ) ; } 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 ; } int tt = 0 ; void get( int node ){ vector < int > v ; FOR( i , N ) if( find( i ) == node ) v.pb( i ) ; for( auto x : v ) create( x ) ; int hs = 0 ; for( auto x : v ){ for( auto y : v ){ if( P[ x ][ y ] == 2 ) hs = 1 ; if( P[ x ][ y ] == 0 ) tt = -1 ; if( P[ x ][ y ] == 1 ) unite( x , y ) ; } } vector < int > vu ; set < int > se ; for( auto x : v ) se.insert( find( x ) ) ; for( auto x : se ){ vector < int > vi ; for( auto y : v ) if( find( y ) == x ) vi.pb( y ) ; FOR( i , vi.size() - 1 ){ pas[ vi[ i ] ][ vi[ i + 1 ] ] = 1 ; pas[ vi[ i + 1 ] ][ vi[ i ] ] = 1 ; } vu.pb( vi[ vi.size() - 1 ] ) ; } if( hs == 1 && v.size() != 1 ) vu.pb( vu[ 0 ] ) ; FOR( i , vu.size() - 1 ){ pas[ vu[ i ] ][ vu[ i + 1 ] ] = 1 ; pas[ vu[ i + 1 ] ][ vu[ i ] ] = 1 ; } } int construct( vector< vector< int > > p ){ N = p.size() ; P = p ; FOR( i , N ) create( i ) ; FOR( i , N ){ FOR( j , N ){ if( p[ i ][ j ] == 0 ) continue ; unite( i , j ) ; } } set < int > se ; FOR( i , N ){ se.insert( find( i ) ) ; } FOR( i , N ){ vector < int > vu ; FOR( i , N ) vu.pb( 0 ) ; pas.pb( vu ) ; } for( auto x : se ) get( x ) ; if( tt == -1 ) return 0 ; build( pas ) ; return 1 ; } // int main() { // assert(scanf("%d", &n) == 1); // p.resize(n); // for (int i = 0; i < n; i++) { // p[i].resize(n); // } // for (int i = 0; i < n; i++) { // for (int j = 0; j < n; j++) { // assert(scanf("%d", &p[i][j]) == 1); // } // } // fclose(stdin); // int possible = construct(p); // check(possible == 0 || possible == 1, "Invalid return value of construct"); // if (possible == 1) { // check(called, "construct returned 1 without calling build"); // } else { // check(!called, "construct called build but returned 0"); // } // printf("OK\n"); // printf("%d\n", possible); // if (possible == 1) { // for (int i = 0; i < n; i++) { // for (int j = 0; j < n; j++) { // if (j) { // printf(" "); // } // printf("%d", b[i][j]); // } // printf("\n"); // } // } // fclose(stdout); // }

Compilation message (stderr)

supertrees.cpp: In function 'void get(int)':
supertrees.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
   97 |         FOR( i , vi.size() - 1 ){
      |              ~~~~~~~~~~~~~~~~~           
supertrees.cpp:97:9: note: in expansion of macro 'FOR'
   97 |         FOR( i , vi.size() - 1 ){
      |         ^~~
supertrees.cpp:12:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
......
  104 |         FOR( i , vu.size() - 1 ){
      |              ~~~~~~~~~~~~~~~~~           
supertrees.cpp:104:9: note: in expansion of macro 'FOR'
  104 |         FOR( i , vu.size() - 1 ){
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...