oj.uz

답안 #102321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102321 2019-03-24T10:19:54 Z groeneprof Ball Machine (BOI13_ballmachine) C++14
100 / 100
 816 ms 33552 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 301 ms 14576 KB Output is correct
3 Correct 148 ms 14840 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 512 KB Output is correct
9 Correct 13 ms 1152 KB Output is correct
10 Correct 74 ms 3960 KB Output is correct
11 Correct 333 ms 14728 KB Output is correct
12 Correct 151 ms 14840 KB Output is correct
13 Correct 216 ms 14604 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 6648 KB Output is correct
2 Correct 658 ms 27356 KB Output is correct
3 Correct 188 ms 21832 KB Output is correct
4 Correct 226 ms 8568 KB Output is correct
5 Correct 242 ms 8440 KB Output is correct
6 Correct 195 ms 8440 KB Output is correct
7 Correct 208 ms 7232 KB Output is correct
8 Correct 73 ms 6520 KB Output is correct
9 Correct 570 ms 27680 KB Output is correct
10 Correct 732 ms 27260 KB Output is correct
11 Correct 403 ms 27128 KB Output is correct
12 Correct 521 ms 24420 KB Output is correct
13 Correct 279 ms 29460 KB Output is correct
14 Correct 188 ms 22000 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 283 ms 14164 KB Output is correct
2 Correct 790 ms 25068 KB Output is correct
3 Correct 597 ms 26872 KB Output is correct
4 Correct 449 ms 22264 KB Output is correct
5 Correct 558 ms 21844 KB Output is correct
6 Correct 510 ms 21980 KB Output is correct
7 Correct 485 ms 19944 KB Output is correct
8 Correct 550 ms 26748 KB Output is correct
9 Correct 619 ms 28024 KB Output is correct
10 Correct 756 ms 27552 KB Output is correct
11 Correct 816 ms 27420 KB Output is correct
12 Correct 783 ms 25068 KB Output is correct
13 Correct 795 ms 33552 KB Output is correct
14 Correct 384 ms 21988 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 615 ms 27812 KB Output is correct
2 Correct 631 ms 24992 KB Output is correct
3 Correct 263 ms 33268 KB Output is correct
4 Correct 626 ms 27896 KB Output is correct
5 Correct 662 ms 27356 KB Output is correct
6 Correct 441 ms 27448 KB Output is correct
7 Correct 638 ms 25096 KB Output is correct
8 Correct 285 ms 33272 KB Output is correct
9 Correct 192 ms 21900 KB Output is correct