Submission #284963

# Submission time Handle Problem Language Result Execution time Memory
284963 2020-08-28T08:30:05 Z Nodir_Bobiev Split the Attractions (IOI19_split) C++17
Compilation error
0 ms 0 KB
    split

    #include <bits/stdc++.h>
     
    using namespace std;
     
    const int N = 1e5 + 100;
    bool sub1 = true, sub2 = true, sub3 = true, sub4 = true;
    int n, m, A, B, C, sz[N];
    vector < int > ans;
    vector < int > gr[N];
    vector < pair < int, int > >cl;
     
    vector < int > Subtask1(){
    	vector < int > ans(n,0);
    	int fath = -1, start = 0;
    	for( int i = 0; i < n; i ++ ){
    		if( gr[i].size() == 1 )start = i;
    	}
    	while( A + B + C > 0 ){
    		if( A > 0 ){
    			ans[start] = 1;
    			A--;
    		}else if( B > 0 ){
    			ans[start] = 2;
    			B --;
    		}else{
    			ans[start] = 3;
    			C --;
    		}
    		if( gr[start][0] != fath ){
    			fath = start;
    			start = gr[start][0];
    		}else if( gr[start].size() > 1 ){
    			fath = start;
    			start = gr[start][1];
    		}
    	}return ans;
    }
    vector < int > Subtask2(){
    	vector < int > ans(n, 3);
    	queue < int > q;
    	q.push(0); ans[0] = 2;B--;
    	while(!q.empty() && B > 0){
    		int v = q.front();q.pop();
    		for( auto to: gr[v] ){
    			if( B > 0 && ans[to] == 3 ){
    				q.push(to); ans[to] = 2; B--;
    			}
    		}
    	}for( int i = 0; i < n; i ++ )if( ans[i] == 3 ){ans[i]=1;break;}
    	return ans;	
    }
    void build( int v, int f ){
    	sz[v] = 1;
    	for( auto to: gr[v] ){
    		if( to != f ){
    			build(to, v);
    			sz[v] += sz[to];
    		}
    	}
    }
    void fil( int v, int f, int x ){
    	if( cl[x].first == 0 ) return;
    	ans[v] = cl[x].second;
    	cl[x].first --;
    	for( auto to: gr[v] ){
    		if( to != f ) fil(to, v, x);
    	}
    }
    bool dfs( int v, int f ){
    	vector < pair < int, int > >children;
    	for( auto to: gr[v] ){
    		children.push_back({sz[to], to});
    	}
    	sort(children.begin(),children.end());
    	for( size_t i = 0; i < children.size(); i ++ ){
    		if( children[i].first >= cl[0].first && sz[v] - children[i].first >= cl[1].first ){
    			fil(children[i].second, v, 0);
    			fil(v, children[i].second, 1);
    			return true;
    		}
    	}
    	for( size_t i = 0; i < children.size(); i ++ ){
    		if( children[i].first >= cl[1].first && sz[v] - children[i].first >= cl[0].first ){
    			fil( children[i].second, v, 1);
    			fil( v, children[i].second, 0);
    			return true;
    		}
    	}
    	for( auto to: gr[v] ){
    		if( to != f ){
    			sz[v] -= sz[to]; sz[to] += sz[v];
    			if( dfs(to,v) ) return true;
    		}
    	}
    	return false;
    }
    vector < int > Subtask3(){
    	throw;
    	cl.push_back({A,1}); cl.push_back({B,2}); cl.push_back({C,3});
    	sort(cl.begin(), cl.end());
    	ans.resize(n); build(0, -1);
    	if( dfs(0,-1) ){
    		for( int i = 0; i < n; i ++ )if( !ans[i] ) ans[i] = cl[2].second;
    	}return ans;
    }
    vector < int > Subtask4(){
    	return {};
    }
     
    vector<int> find_split(int nn, int aa, int bb, int cc, vector<int> pp, vector<int> qq) {
    	n = nn; m = pp.size(); A = aa; B = bb; C = cc;
    	if( m >= n )sub3 = false;
    	if( n > 2500 || m > 5000 ) sub4 = false;
    	if( A > 1 ) sub2 = false;
     
    	for( int i = 0; i < m; i ++ ){
    		gr[pp[i]].push_back(qq[i]);
    		gr[qq[i]].push_back(pp[i]);
    	}
    	for( int i = 0; i < n; i ++ ){
    		if( gr[i].size() > 2 )sub1 = false;
    	}
    	if( sub1 ){
    		return Subtask1();
    	}
    	if( sub2 ){
    		return Subtask2();
    	}
    	if( sub3 ){
    		return Subtask3();
    	}
    	if( sub4 ){
    		return Subtask4();
    	}
    	return {};
    }

Compilation message

split.cpp:2:5: error: 'split' does not name a type
    2 |     split
      |     ^~~~~
In file included from /usr/include/c++/9/cmath:43,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/ext/type_traits.h:162:35: error: 'bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  162 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/9/ext/type_traits.h:157:5: note: previous declaration 'template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)'
  157 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/9/ext/type_traits.h:162:26: error: 'nullptr_t' is not a member of 'std'
  162 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/type_traits:361:26: error: 'std::size_t' has not been declared
  361 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/9/type_traits:362:25: error: '_Size' was not declared in this scope
  362 |     struct is_array<_Tp[_Size]>
      |                         ^~~~~
/usr/include/c++/9/type_traits:362:31: error: template argument 1 is invalid
  362 |     struct is_array<_Tp[_Size]>
      |                               ^
/usr/include/c++/9/type_traits:560:42: error: 'nullptr_t' is not a member of 'std'
  560 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                          ^~~~~~~~~
/usr/include/c++/9/type_traits:560:51: error: template argument 1 is invalid
  560 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                                   ^
/usr/include/c++/9/type_traits:1253:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1253 |     : public integral_constant<std::size_t, alignof(_Tp)> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:32,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/type_traits:1253:57: error: template argument 1 is invalid
 1253 |     : public integral_constant<std::size_t, alignof(_Tp)> { };
      |                                                         ^
/usr/include/c++/9/type_traits:1253:57: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1258:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1258 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:32,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/type_traits:1258:46: error: template argument 1 is invalid
 1258 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/9/type_traits:1258:46: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1260:26: error: 'std::size_t' has not been declared
 1260 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/9/type_traits:1261:21: error: '_Size' was not declared in this scope
 1261 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/9/type_traits:1261:27: error: template argument 1 is invalid
 1261 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/9/type_traits:1262:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1262 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:32,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/type_traits:1262:65: error: template argument 1 is invalid
 1262 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/9/type_traits:1262:65: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1266:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1266 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:32,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/type_traits:1266:65: error: template argument 1 is invalid
 1266 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/9/type_traits:1266:65: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1271:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1271 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:32,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/type_traits:1271:46: error: template argument 1 is invalid
 1271 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/9/type_traits:1271:46: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1273:42: error: 'std::size_t' has not been declared
 1273 |   template<typename _Tp, unsigned _Uint, std::size_t _Size>
      |                                          ^~~
/usr/include/c++/9/type_traits:1274:23: error: '_Size' was not declared in this scope
 1274 |     struct extent<_Tp[_Size], _Uint>
      |                       ^~~~~
/usr/include/c++/9/type_traits:1274:36: error: template argument 1 is invalid
 1274 |     struct extent<_Tp[_Size], _Uint>
      |                                    ^
/usr/include/c++/9/type_traits:1275:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1275 |     : public integral_constant<std::size_t,
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:32,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/type_traits:1276:24: error: '_Size' was not declared in this scope
 1276 |           _Uint == 0 ? _Size : extent<_Tp,
      |                        ^~~~~
/usr/include/c++/9/type_traits:1277:28: error: template argument 1 is invalid
 1277 |           _Uint - 1>::value>
      |                            ^
/usr/include/c++/9/type_traits:1277:28: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1282:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1282 |     : public integral_constant<std::size_t,
      |                                     ^~~~~~
In file included from /usr/include/stdlib.h:32,
                 from /usr/include/c++/9/bits/std_abs.h:38,
                 from /usr/include/c++/9/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/lib/gcc/x86_64-linux-gnu/9/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/type_traits:1284:31: error: template argument 1 is invalid
 1284 |              _Uint - 1>::value>
      |                               ^
/usr/include/c++/9/type_traits:1284:31: note: invalid template non-type parameter
/usr/include/c++/9/type_traits:1838:26: error: 'std::size_t' has not been declared
 1838 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/9/type_traits:1839:30: error: '_Size' was not declared in this scope
 1839 |     struct remove_extent<_Tp[_Size]>
      |                              ^~~~~
/usr/include/c++/9/type_traits:1839:36: error: template argument 1 is invalid
 1839 |     struct remove_extent<_Tp[_Size]>
      |                                    ^
/usr/include/c++/9/type_traits:1851:26: error: 'std::size_t' has not been declared
 1851 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/9/type_traits:1852:35: error: '_Size' was not declared in this scope
 1852 |     struct remove_all_extents<_Tp[_Size]>
      |                                   ^~~~~
/usr/include/c++/9/type_traits:1852:41: error: template argument 1 is invalid
 1852 |     struct remove_all_extents<_Tp[_Size]>
      |                                         ^
/usr/include/c++/9/type_traits:1910:12: error: 'std::size_t' has not been declared
 1910 |   template<std::size_t _Len>
      |            ^~~
/usr/include/c++/9/type_traits:1915:23: error: '_Len' was not declared in this scope
 1915 |  unsigned char __data[_Len];
      |                       ^~~~
/usr/include/c++/9/type_traits:1930:12: error: 'std::size_t' has not been declared
 1930 |   template<std::size_t _Len, std::size_t _Align =
      |            ^~~
/usr/include/c++/9/type_traits:1930:30: error: 'std::size_t' has not been declared
 1930 |   template<std::size_t _Len, std::size_t _Align =
      |                              ^~~
/usr/include/c++/9/type_traits:1931:48: error: '_Len' was not declared in this scope
 1931 |     __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                ^~~~
/usr/include/c++/9/type_traits:1931:52: error: template argument 1 is invalid
 1931 |     __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                    ^
/usr/include/c++/9/type_traits:1936:23: error: '_Len' was not declared in this scope
 1936 |  unsigned char __data[_Len];
      |                       ^~~~
/usr/include/c++/9/type_traits:1937:37: error: '_Align' was not declared in this scope
 1937 |  struct __attribute__((__aligned__((_Align)))) { } __align;
      |                                     ^~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/bits/stl_pair.h:86:12: error: 'std::size_t' has not been declared
   86 |   template<std::size_t...>
      |            ^~~
/usr/include/c++/9/bits/stl_pair.h:434:36: error: 'std::size_t' has not been declared
  434 |       template<typename... _Args1, std::size_t... _Indexes1,
      |                                    ^~~
/usr/include/c++/9/bits/stl_pair.h:435:36: error: 'std::size_t' has not been declared
  435 |                typename... _Args2, std::size_t... _Indexes2>
      |                                    ^~~
/usr/include/c++/9/bits/stl_pair.h:437:27: error: '_Indexes1' was not declared in this scope
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                           ^~~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:437:36: error: expected parameter pack before '...'
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                                    ^~~
/usr/include/c++/9/bits/stl_pair.h:437:39: error: template argument 1 is invalid
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                                       ^
/usr/include/c++/9/bits/stl_pair.h:437:55: error: '_Indexes2' was not declared in this scope
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                                                       ^~~~~~~~~
/usr/include/c++/9/bits/stl_pair.h:437:64: error: expected parameter pack before '...'
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                                                                ^~~
/usr/include/c++/9/bits/stl_pair.h:437:67: error: template argument 1 is invalid
  437 |              _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
      |                                                                   ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:65,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/bits/stl_iterator_base_types.h:116:67: error: 'ptrdiff_t' does not name a type
  116 |   template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
      |                                                                   ^~~~~~~~~
In file included from /usr/include/c++/9/bits/stl_algobase.h:65,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/bits/stl_iterator_base_types.h:1:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
  +++ |+#include <cstddef>
    1 | // Types used in iterator implementation -*- C++ -*-
In file included from /usr/include/c++/9/bits/stl_algobase.h:65,
                 from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from split.cpp:4:
/usr/include/c++/9/bits/stl_iterator_base_types.h:182:15: error: 'ptrdiff_t' does not name a type
  182 |       typedef ptrdiff_t                   difference_type;
      |               ^~~~~~~~~
/usr/include/c++/9/bits/stl_iterator_base_types.h:182:15: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
/usr/include/c++/9/bits/stl_iterator_base_types.h:193:15: error: 'ptrdiff_t' does not name a type
  193 |       typedef ptrdiff_t                   difference_type;
      |               ^~~~~~~~~
/usr/include/c++/9/bits/stl_iterator_base_types.h:193:15: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you