Submission #102321

#	Time	Username	Problem	Language	Result	Execution time	Memory
102321		groeneprof	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	816 ms	33552 KiB

ballmachine

#include <bits/stdc++.h>
//#define int long long
#define P(x) do {if(debug) cout << x << endl;} while(false)
#define H(x) P(#x << ": " << x)
#define FR(i, a, b) for(int i = (a); i < (b); ++i)
#define F(i, n) FR(i, 0, n)
#define DR(i, a, b) for(int i = (b); i --> (a);)
#define D(i, n) DR(i, 0, n)
#define S(s) (int)(s).size()
#define ALL(x) (x).begin(), (x).end()
#define MI(x, a) (x) = min(x, a)
#define MA(x, a) (x) = max(x, a)
#define V vector
#define pb push_back
#define mp make_pair
using namespace std;
const bool debug = 0;
vector<vector<int> > graph;
vector<int> order, parent, depth;
set<pair<int,int> > notfilled;
int N, n, Q, q, root;
vector<bool> filled;
vector<vector<int> > memo;
int graphsort(int u){
	vector<pair<int,int> > vv;
	for(int v : graph[u]){
		vv.push_back(mp(graphsort(v), v));
	}
	sort(vv.begin(), vv.end());
	int mi = u;
	F(i,graph[u].size()){
		mi = min(mi, vv[i].first);
		graph[u][i] = vv[i].second;
	}
	return mi;
}
void dfs(int u, int& i, int d){
	for(int v : graph[u]){
		dfs(v, i, d+1);
	}
	depth[u]=d;
	P("insert "<<i<<" "<<u);
	notfilled.insert(mp(i, u));
	order[u]=i++;
}
int add_k(int k){
	int lastpos;
	F(i, k){
		lastpos= (*notfilled.begin()).second;
		P(i<<" "<<lastpos);
		filled[lastpos] = true;
		notfilled.erase(notfilled.begin());
	}
	return lastpos;
}

int f(int u, int p2){
	if(p2==0) return parent[u];
	if(memo[u][p2] != -1) return memo[u][p2];
	return memo[u][p2] = f(f(u, p2-1), p2-1);
}

int remove(int u){
	int v = u;
	for(int bs = 19; bs>=0; bs--){
		if(filled[f(v, bs)]){
			v = f(v,bs);
			P(v<<" is too low");
		}
	}
	P(v<<" is highest "); 		
	filled[v]=false;
	notfilled.insert(mp(order[v], v));
	return depth[u]-depth[v];

}

signed main() {
	ios_base::sync_with_stdio(true);
	cin.tie(0);
	cin>>N>>Q;
	n = N; q = Q;
	graph.resize(n);
	parent.resize(n);
	order.resize(n);
	depth.resize(n);
	filled.resize(n, false);
	memo.resize(n+10, vector<int>(21, -1));
	F(i, N){
		int a;
		cin>>a;
		a--;
		parent[i]=a;
		if(a==-1){
			root = i;
			parent[i]=i;
			continue;
		}
		graph[a].push_back(i);
	}
	graphsort(root);
	int xxxx = 0;
	dfs(root, xxxx, 0);
	F(i, q){
		P("Hellooo");
		int t;
		cin>>t;
		int a;
		cin>>a;
		P("Hello aaaa");
		if(t==1){
			cout<<add_k(a)+1<<"\n";
		}
		else{
			cout<<remove(a-1)<<"\n";
		}
	}
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int graphsort(int)':
ballmachine.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FR(i, a, b) for(int i = (a); i < (b); ++i)
                                        ^
ballmachine.cpp:6:17: note: in expansion of macro 'FR'
 #define F(i, n) FR(i, 0, n)
                 ^~
ballmachine.cpp:31:2: note: in expansion of macro 'F'
  F(i,graph[u].size()){
  ^
ballmachine.cpp: In function 'int add_k(int)':
ballmachine.cpp:54:9: warning: 'lastpos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return lastpos;
         ^~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5