Submission #102319

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
102319	2019-03-24T10:16:36 Z	groeneprof	Ball Machine (BOI13_ballmachine)	C++14	91.4286 / 100	1000 ms	33656 KB

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<<endl;
		}
		else{
			cout<<remove(a-1)<<endl;
		}
	}
	return 0;
}

Compilation message

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.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	500 ms	14872 KB	Output is correct
3	Correct	298 ms	14808 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	5 ms	512 KB	Output is correct
7	Correct	5 ms	512 KB	Output is correct
8	Correct	8 ms	512 KB	Output is correct
9	Correct	33 ms	1280 KB	Output is correct
10	Correct	87 ms	3932 KB	Output is correct
11	Correct	490 ms	14704 KB	Output is correct
12	Correct	295 ms	14872 KB	Output is correct
13	Correct	414 ms	14816 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	6508 KB	Output is correct
2	Correct	817 ms	27276 KB	Output is correct
3	Correct	325 ms	21936 KB	Output is correct
4	Correct	313 ms	8568 KB	Output is correct
5	Correct	341 ms	8440 KB	Output is correct
6	Correct	291 ms	8656 KB	Output is correct
7	Correct	318 ms	7288 KB	Output is correct
8	Correct	182 ms	6612 KB	Output is correct
9	Correct	651 ms	27744 KB	Output is correct
10	Correct	837 ms	27124 KB	Output is correct
11	Correct	564 ms	27324 KB	Output is correct
12	Correct	634 ms	24316 KB	Output is correct
13	Correct	370 ms	29432 KB	Output is correct
14	Correct	314 ms	21884 KB	Output is correct

Subtask #3

31.4285714286 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	338 ms	14168 KB	Output is correct
2	Correct	890 ms	25208 KB	Output is correct
3	Correct	665 ms	26848 KB	Output is correct
4	Correct	498 ms	22432 KB	Output is correct
5	Correct	540 ms	22012 KB	Output is correct
6	Correct	573 ms	21880 KB	Output is correct
7	Correct	529 ms	19992 KB	Output is correct
8	Correct	630 ms	26776 KB	Output is correct
9	Correct	758 ms	27840 KB	Output is correct
10	Correct	944 ms	27516 KB	Output is correct
11	Execution timed out	1040 ms	27512 KB	Time limit exceeded
12	Execution timed out	1022 ms	25192 KB	Time limit exceeded
13	Execution timed out	1059 ms	33656 KB	Time limit exceeded
14	Correct	552 ms	22104 KB	Output is correct

Subtask #4

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	732 ms	28008 KB	Output is correct
2	Correct	833 ms	25212 KB	Output is correct
3	Correct	406 ms	33180 KB	Output is correct
4	Correct	698 ms	27896 KB	Output is correct
5	Correct	710 ms	27512 KB	Output is correct
6	Correct	539 ms	27532 KB	Output is correct
7	Correct	779 ms	25208 KB	Output is correct
8	Correct	376 ms	33264 KB	Output is correct
9	Correct	301 ms	21864 KB	Output is correct