Submission #102318

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
102318	2019-03-24T10:12:08 Z	groeneprof	Ball Machine (BOI13_ballmachine)	C++14	91.4286 / 100	1000 ms	44744 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 'long long int graphsort(long long 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 'long long int add_k(long long 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	3 ms	384 KB	Output is correct
2	Correct	579 ms	21724 KB	Output is correct
3	Correct	350 ms	21820 KB	Output is correct
4	Correct	3 ms	256 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	4 ms	640 KB	Output is correct
7	Correct	5 ms	640 KB	Output is correct
8	Correct	6 ms	640 KB	Output is correct
9	Correct	31 ms	1664 KB	Output is correct
10	Correct	95 ms	5752 KB	Output is correct
11	Correct	526 ms	21832 KB	Output is correct
12	Correct	296 ms	21752 KB	Output is correct
13	Correct	450 ms	21624 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	261 ms	8780 KB	Output is correct
2	Correct	808 ms	37864 KB	Output is correct
3	Correct	335 ms	32624 KB	Output is correct
4	Correct	358 ms	11904 KB	Output is correct
5	Correct	358 ms	11896 KB	Output is correct
6	Correct	322 ms	11860 KB	Output is correct
7	Correct	332 ms	10360 KB	Output is correct
8	Correct	208 ms	8928 KB	Output is correct
9	Correct	746 ms	38264 KB	Output is correct
10	Correct	898 ms	38008 KB	Output is correct
11	Correct	589 ms	37944 KB	Output is correct
12	Correct	780 ms	34716 KB	Output is correct
13	Correct	403 ms	39196 KB	Output is correct
14	Correct	343 ms	32776 KB	Output is correct

Subtask #3

31.4285714286 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	392 ms	19676 KB	Output is correct
2	Correct	922 ms	36472 KB	Output is correct
3	Correct	713 ms	35704 KB	Output is correct
4	Correct	556 ms	30712 KB	Output is correct
5	Correct	595 ms	30456 KB	Output is correct
6	Correct	679 ms	30664 KB	Output is correct
7	Correct	645 ms	29064 KB	Output is correct
8	Correct	698 ms	35636 KB	Output is correct
9	Correct	915 ms	38572 KB	Output is correct
10	Execution timed out	1071 ms	38140 KB	Time limit exceeded
11	Correct	994 ms	38700 KB	Output is correct
12	Execution timed out	1037 ms	36600 KB	Time limit exceeded
13	Execution timed out	1043 ms	44744 KB	Time limit exceeded
14	Correct	645 ms	32988 KB	Output is correct

Subtask #4

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	892 ms	38520 KB	Output is correct
2	Correct	962 ms	36472 KB	Output is correct
3	Correct	515 ms	44396 KB	Output is correct
4	Correct	828 ms	38632 KB	Output is correct
5	Correct	895 ms	38144 KB	Output is correct
6	Correct	637 ms	38396 KB	Output is correct
7	Correct	968 ms	36396 KB	Output is correct
8	Correct	474 ms	44384 KB	Output is correct
9	Correct	399 ms	32736 KB	Output is correct