Submission #946508

#	Time	Username	Problem	Language	Result	Execution time	Memory
946508		PM1	Watermelon (INOI20_watermelon)	C++17	Compilation error	0 ms	0 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
const int mxn=1e5+5;
int n,k,a[mxn],par[mxn],ans=0,res[mxn],mx,dis[mxn],sz[mxn];
vector<int>v[mxn],state[mxn];
set<int>s;
set<pair<int,int>>tree;
bool mark[mxn];
void dfs(int z){
	bool cnt=0;
	for(auto i:v[z]){
		if(par[z]!=i){
			cnt=1;
			dfs(i);
			sz[z]++;
		}
	}
	if(!cnt)s.insert(z);
}
void solve(int x=1){
	if(x==n+1){
		ans++;
		return;
	}
	auto y=s.upper_bound(0);
	while(y!=s.end()){
		int z=*y;
		s.erase(z);
		sz[par[z]]--;
		if(!sz[par[z]])
			s.insert(par[z]);
		solve(x+1);
		s.insert(z);
		sz[par[z]]++;
		if(sz[par[z]])
			s.erase(par[z]);
		y=s.upper_bound(z);
		if(ans==k){
			res[z]=x;
			break;
		}
	}
}
void make(int x,int y){
	//cout<<x<<" "<<y<<'\n';
	par[y]=x;
	tree.insert({x,a[x]});
	tree.insert({y,a[y]});
	v[x].push_back(y);
	v[y].push_back(x);
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==-1){
			state[n+1].push_back(i);
			a[i]=n+1;
		}
		else{
			state[a[i]].push_back(i);
			mx=max(mx,a[i]);
		}
	}
	for(int i=1;i<state[n+1].size();i++){
		make(state[n+1][i-1],state[n+1][i]);
	}
	tree.insert({stat[n+1][0],n+1});
	while(mx){
		if(state[mx].size()==0){
			cout<<-1;
			return 0;
		}
		reverse(state[mx].begin(),state[mx].end());
		for(auto i:state[mx]){
			auto x=tree.lower_bound(make_pair(i,0));
			if(x==tree.end()){
				x--;
				make(x->fr,i);
				continue;
			}
			if(x==tree.begin()){
				make(x->fr,i);
				continue;
			}
			auto y=x;
			y--;
			if(x->sc>y->sc)
				make(y->fr,i);
			else if(x->sc<y->sc)
				make(x->fr,i);
			else{
				if(y->sc==n+1)
					make(x->fr,i);
				else
					make(y->fr,i);
			}
		}
		mx--;
	}
	dfs(state[n+1][0]);
	solve();
	if(ans<k){
		cout<<-1;
	}
	else{

		for(int i=1;i<=n;i++){
			cout<<res[i]<<" ";
		}
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i=1;i<state[n+1].size();i++){
      |              ~^~~~~~~~~~~~~~~~~~
Main.cpp:70:15: error: 'stat' was not declared in this scope; did you mean 'state'?
   70 |  tree.insert({stat[n+1][0],n+1});
      |               ^~~~
      |               state
Main.cpp:70:32: error: no matching function for call to 'std::set<std::pair<int, int> >::insert(<brace-enclosed initializer list>)'
   70 |  tree.insert({stat[n+1][0],n+1});
      |                                ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_set.h:509:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<int, int>]'
  509 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:509:32: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, int>&'}
  509 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:518:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<int, int>]'
  518 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:518:27: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
  518 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:546:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<int, int>]'
  546 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:546:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_set.h:551:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<int, int>]'
  551 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:551:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_set.h:566:2: note: candidate: 'template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  566 |  insert(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_set.h:566:2: note:   template argument deduction/substitution failed:
Main.cpp:70:32: note:   candidate expects 2 arguments, 1 provided
   70 |  tree.insert({stat[n+1][0],n+1});
      |                                ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_set.h:578:7: note: candidate: 'void std::set<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]'
  578 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:578:43: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::initializer_list<std::pair<int, int> >'
  578 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:598:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::insert_return_type std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::node_type&&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::insert_return_type = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::insert_return_type; std::set<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::node_type]'
  598 |       insert(node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:598:26: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::pair<int, int> >::node_type&&' {aka 'std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::node_type&&'}
  598 |       insert(node_type&& __nh)
      |              ~~~~~~~~~~~~^~~~
/usr/include/c++/10/bits/stl_set.h:603:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::node_type&&) [with _Key = std::pair<int, int>; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::less<std::pair<int, int> >, std::allocator<std::pair<int, int> > >::node_type]'
  603 |       insert(const_iterator __hint, node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:603:7: note:   candidate expects 2 arguments, 1 provided