제출 #790117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790117		lollipop	Simurgh (IOI17_simurgh)	C++17	0 / 100	5 ms	9684 KiB

simurgh

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int 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 = 2e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "simurgh.h"


// static int MAXQ = 30000;

// static int n, m, q = 0;
// static vector<int> u, v;
// static vector<bool> goal;
// static vector<int> parent;

// static int find(int node) {
// 	return (parent[node] == node ? node : parent[node] = find(parent[node]));
// }
// static bool merge(int v1, int v2) {
// 	v1 = find(v1);
// 	v2 = find(v2);
// 	if (v1 == v2)
// 		return false;
// 	parent[v1] = v2;
// 	return true;
// }
// static void wrong_answer() {
// 	printf("NO\n");
// 	exit(0);
// }
// static bool is_valid(const vector<int>& r) {
// 	if(int(r.size()) != n - 1)
// 		return false;

// 	for(int i = 0; i < n - 1; i++)
// 		if(r[i] < 0 || r[i] >= m)
// 			return false;

// 	parent.resize(n);
// 	for (int i = 0; i < n; i++) {
// 		parent[i] = i;
// 	}
// 	for (int i = 0; i < n - 1; i++) {
// 		if (!merge(u[r[i]], v[r[i]])) {
// 			return false;
// 		}
// 	}
// 	return true;
// }
// static int _count_common_roads_internal(const vector<int>& r) {
// 	if (!is_valid(r))
// 		wrong_answer();

// 	int common = 0;
// 	for(int i = 0; i < n - 1; i++) {
// 		bool is_common = goal[r[i]];
// 		if (is_common)
// 			common++;
// 	}

// 	return common;	
// }
// int count_common_roads(const vector<int>& r) {
// 	q++;
// 	if(q > MAXQ)
// 		wrong_answer();

// 	return _count_common_roads_internal(r);
// }



int pp[ N ] , ss[ N ] ; 
void create( int node ){
     pp[ node ] = node ;
	 ss[ node ] = 1 ; 
	 return ; 
}
int findd( int node ){
	if( pp[ node ] == node ) return node ;
	return pp[ node ] = findd( pp[ node ] ) ;
}
void unite( int a , int b ){
	 if( ss[ a ] < ss[ b ] ) swap( a , b ) ; 
	 if( ss[ a ] == ss[ b ] ) ss[ a ] ++ ; 
	 pp[ b ] = a ;
	 return ;  
}
int gd[ N ] ; 
vector < int > V[ N ] ;
vector < int > rod[ N ] ; 
int hs[ N ] , son[ N ] ;
int ddf( int node , int ppp ){
     int tt = -1 ; 
	 int test = 0 ; 
	 for( auto x : V[ node ] ){
        if( x == ppp ) continue ; 
        tt = max( tt , ddf( x , node ) ) ;
		if( son[ x ] == -1 ) test = -1 ; 
	 }
	 if( test == 0 && gd[ node ] == 0 ) tt = node ; 
	 if( gd[ node ] != 1 ) test = -1 ; 
	 son[ node ] = test ;
	 return tt ; 
}
int titu[ N ] ; 
vector<int> find_roads(int n, vector<int> u, vector<int> vv){
	  FOR( i , u.size() ){
		  rod[ u[ i ] ].pb( i ) ;
		  rod[ vv[ i ] ].pb( i ) ;  
	  }
	  vector < int > ans ; 
      while( ans.size() != n - 1 ){
		  vector < int > cur ; 
		  FOR( i , n ) create( i ) , V[ i ].clear() ; 
          for( auto x : ans ){
			 hs[ x ] = 1 ; 
             V[ u[ x ] ].pb( vv[ x ] ) ;
			 V[ vv[ x ] ].pb( u[ x ] ) ;
			 int a = u[ x ] , b = vv[ x ] ;
			 cur.pb( x ) ;
			 a = findd( a ) ; 
			 b = findd( b ) ; 
			 unite( a , b ) ; 
		  }
		  FOR( i , n ){
			  if( hs[ i ] == 1 ) continue ; 
			  int a = u[ i ] , b = vv[ i ] ;
			  int A = a , B = b ; 
			  a = findd( a ) ; b = findd( b ) ;
			  if( a == b ) continue ;
			  cur.pb( i ) ; 
              unite( a , b ) ;
			  V[ A ].pb( B ) ; V[ B ].pb( A ) ; 
		  }
		  int node = ddf( 0 , - 1 ) ; 
		  int axla = count_common_roads( cur ) ;
		  if( axla == n - 1 ){
			  ans = cur ; break ; 
		  }
          for( auto x : rod[ node ] ){
			  titu[ x ] = 1 ;
		  }
         FOR( i , cur.size() ){
			 if( titu[ cur[ i ] ] == 1 && hs[ cur[ i ] ] == 0 ){
				 cur.erase( cur.begin() + i ) ; 
				 break ; 
			 }
		 }
         pair < int , int > mx = { -1 , -1 } ; 
         for( auto x : rod[ node ] ){
             if( hs[ x ] == 0 && count( cur.begin() , cur.end() , x ) != false ){
				 cur.pb( x ) ; 
				 int axla = count_common_roads( cur ) ;
				 cur.pop_back() ; 
				 if( axla > mx.f ){
					 mx = { axla , x } ; 
				 }
			 }
			 titu[ x ] = 0 ; 
		 }
		 ans.pb( mx.s ) ;
		 gd[ node ] = 1 ; 
	  }
	  sort( ans.begin() , ans.end() ) ;
	  return ans ; 
}



// int main() {
// 	assert(2 == scanf("%d %d", &n, &m));
// 	assert(1 == scanf("%d", &MAXQ));

// 	u.resize(m);
// 	v.resize(m);

// 	for(int i = 0; i < m; i++)
// 		assert(2 == scanf("%d %d", &u[i], &v[i]));

// 	goal.resize(m, false);

// 	for(int i = 0; i < n - 1; i++) {
// 		int id;
// 		assert(1 == scanf("%d", &id));
// 		goal[id] = true;
// 	}

// 	vector<int> result = find_roads(n, u, v);

// 	if(_count_common_roads_internal(result) != n - 1)
// 		wrong_answer();
		
//     printf("OK\n");
// 	for(int i = 0; i < (int)result.size(); i++){
// 		if(i)
// 			printf(" ");
// 		printf("%d", result[i]);
// 	}
// 	printf("\n");

// 	return 0;
// }

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.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 ++ )
......
  134 |    FOR( i , u.size() ){
      |         ~~~~~~~~~~~~                     
simurgh.cpp:134:4: note: in expansion of macro 'FOR'
  134 |    FOR( i , u.size() ){
      |    ^~~
simurgh.cpp:139:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |       while( ans.size() != n - 1 ){
      |              ~~~~~~~~~~~^~~~~~~~
simurgh.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 ++ )
......
  170 |          FOR( i , cur.size() ){
      |               ~~~~~~~~~~~~~~             
simurgh.cpp:170:10: note: in expansion of macro 'FOR'
  170 |          FOR( i , cur.size() ){
      |          ^~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30