oj.uz

Submission #111382

# Submission time Handle Problem Language Result Execution time Memory
111382 2019-05-15T05:02:11 Z rajarshi_basu Ball Machine (BOI13_ballmachine) C++14
Compilation error
 0 ms 0 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>
#include <fstream>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<ll,ll>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 

const ll INF = 4e18;
using namespace std;
const int MAXN = 100005;

vi g[MAXN];
int sparseTable[20][MAXN];
int DPmin[MAXN];
int dpt[MAXN];
int parent[MAXN];
set<ii> s;
int status[MAXN];

void dfs1(int node,int p){
	dpt[node] = ((p!=-1)?dpt[p]+1:0);
	parent[node] = p;
	vector<ii> all;
	DPmin[node] = node;
	for(auto e:g[node]){
		if(e==p)continue;
		dfs1(e,node);
		all.pb({DPmin[e],e});
		DPmin[node] = min(DPmin[node],DPmin[e]);
	}
	sort(all.begin(), all.end());
	g[node].clear();
	for(auto e:all)g[node].pb(e.ss);
	g[node].pb(p);
}
int T = 0;
int tm[MAXN];
void dfs2(int node,int p){
	for(auto e:g[node]){
		if(e!=p)dfs2(e,node);
	}
	tm[node] = T;
	s.insert({T++,node});
}
void buildSparseTable(int n){
	FOR(i,n)sparseTable[0][i] = parent[i];
	FORE(i,1,19){
		FOR(node,n){
			int p = sparseTable[i-1][node];
			if(p == -1){
				sparseTable[i][node] = -1;
			}else{
				sparseTable[i][node] = sparseTable[i-1][p];
			}
		}
		
	}
}
inline int findFirstAncestor(int n,int a){
	int k = 20;

	while(k--){
		int p = sparseTable[k][a];
		if(p == -1 or status[p] == 0){

		}else{
			a=p;
		}
	}
	return a;
}


int main(){
	int n,q;
	cin >> n >> q;
	FOR(i,n){
		int a;
		cin >> a;
		a--;
		if(a >= 0)g[a].pb(i);
	}
	dfs1(0,-1);
	dfs2(0,-1);
	buildSparseTable(n);
	while(q--){
		int t,a;
		cin >> t >> a;
		if(t == 1){
			int last = 0;
			FOR(i,a){
				ii to = *s.begin();
				s.erase(to);
				status[to.ss] = 1;
				last = to.ss+1;
			}
			cout << last << endl;
		}else{

			a--;
			int p = findFirstAncestor(n,a);
			s.insert({tm[p],p});
			status[p] = 0;
			
			cout << dpt[a]-dpt[p] << endl;
		}
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'void dfs2(int, int)':
ballmachine.cpp:63:2: error: reference to 'tm' is ambiguous
  tm[node] = T;
  ^~
ballmachine.cpp:58:5: note: candidates are: int tm [100005]
 int tm[MAXN];
     ^~
In file included from /usr/include/pthread.h:24:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/gthr-default.h:35,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/gthr.h:148,
                 from /usr/include/c++/7/ext/atomicity.h:35,
                 from /usr/include/c++/7/bits/ios_base.h:39,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from ballmachine.cpp:1:
/usr/include/time.h:133:8: note:                 struct tm
 struct tm
        ^~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:123:14: error: reference to 'tm' is ambiguous
    s.insert({tm[p],p});
              ^~
ballmachine.cpp:58:5: note: candidates are: int tm [100005]
 int tm[MAXN];
     ^~
In file included from /usr/include/pthread.h:24:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/gthr-default.h:35,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/gthr.h:148,
                 from /usr/include/c++/7/ext/atomicity.h:35,
                 from /usr/include/c++/7/bits/ios_base.h:39,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from ballmachine.cpp:1:
/usr/include/time.h:133:8: note:                 struct tm
 struct tm
        ^~
ballmachine.cpp:123:22: error: no matching function for call to 'std::set<std::pair<long long int, long long int> >::insert(<brace-enclosed initializer list>)'
    s.insert({tm[p],p});
                      ^
In file included from /usr/include/c++/7/set:61:0,
                 from ballmachine.cpp:3:
/usr/include/c++/7/bits/stl_set.h:499:7: note: candidate: std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _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<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]
       insert(const value_type& __x)
       ^~~~~~
/usr/include/c++/7/bits/stl_set.h:499:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type& {aka const std::pair<long long int, long long int>&}'
/usr/include/c++/7/bits/stl_set.h:508:7: note: candidate: std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _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<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]
       insert(value_type&& __x)
       ^~~~~~
/usr/include/c++/7/bits/stl_set.h:508:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::pair<long long int, long long int> >::value_type&& {aka std::pair<long long int, long long int>&&}'
/usr/include/c++/7/bits/stl_set.h:536: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<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]
       insert(const_iterator __position, const value_type& __x)
       ^~~~~~
/usr/include/c++/7/bits/stl_set.h:536:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/7/bits/stl_set.h:541: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<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, long long int>]
       insert(const_iterator __position, value_type&& __x)
       ^~~~~~
/usr/include/c++/7/bits/stl_set.h:541:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/7/bits/stl_set.h:556:2: note: candidate: template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]
  insert(_InputIterator __first, _InputIterator __last)
  ^~~~~~
/usr/include/c++/7/bits/stl_set.h:556:2: note:   template argument deduction/substitution failed:
ballmachine.cpp:123:22: note:   candidate expects 2 arguments, 1 provided
    s.insert({tm[p],p});
                      ^
In file included from /usr/include/c++/7/set:61:0,
                 from ballmachine.cpp:3:
/usr/include/c++/7/bits/stl_set.h:568:7: note: candidate: void std::set<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]
       insert(initializer_list<value_type> __l)
       ^~~~~~
/usr/include/c++/7/bits/stl_set.h:568:7: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::initializer_list<std::pair<long long int, long long int> >'