oj.uz

답안 #30975

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30975 2017-08-02T12:54:55 Z Mamnoon_Siam Ball Machine (BOI13_ballmachine) C++14
20.989 / 100
 606 ms 30072 KB 
#include <bits/stdc++.h>
using namespace std;

#define lc (node<<1)
#define rc ((node<<1)|1)
#define mid ((b+e)>>1)

int par[100010], T[400040];
vector<int> v[100010]; int root;
int cntr=1; int a[100010], depth[100010];
bool all[400040]; int n, Q;
int table[20][100010], where[100010];
int auxilary[100010];

int dfs(int u) {
	if(v[u].size()==0) return u;
	vector<pair<int, int>> temp;
	for(auto b : v[u]) temp.push_back({dfs(b), b});
	sort(temp.begin(), temp.end()); v[u].clear();
	for(auto b : temp) v[u].push_back(b.second);
	return min(u, temp[0].first);
}

void make_arr(int u) {
	if(v[u].size()==0) { a[cntr++]=u; return ; }
	for(auto b : v[u]) make_arr(b);
	a[cntr++] = u; where[u]=cntr-1; return ;
}

void calc_depth(int u, int d) { depth[u]=d; for(auto b : v[u]) calc_depth(b, d+1); }

void remove(int node, int b, int e, int pos) {
	if(e<pos || b>pos) return ;
	if(b==e) { all[node]=false; T[node]=0; return ; }
	if(all[node]) {
		all[lc]=all[rc]=true; all[node]=false;
		T[lc]=mid-b+1; T[rc]=e-mid;
	}
	remove(lc, b, mid, pos); remove(rc, mid+1, e, pos);
	T[node]=T[lc]+T[rc];
}

void update(int node, int b, int e, int i, int j) {
	if(b>j || e<i) return ;
	if(i<=b && e<=j) { all[node]=true; T[node]=e-b+1; return ; }
	update(lc, b, mid, i, j); update(rc, mid+1, e, i, j);
	T[node]=T[lc]+T[rc];
}

int range_query(int node, int b, int e, int i, int j) {
	if(e<i || b>j) return 0;
	if(i<=b && e<=j) return T[node];
	if(all[node]==true) {
		all[lc]=all[rc]=true; all[node]=false;
		T[lc]=mid-b+1; T[rc]=e-mid;
	}
	return range_query(lc, b, mid, i, j)+range_query(rc, mid+1, e, i, j);
}

int single_query(int pos) {
	if(pos==0 || pos==-1) return 0;
	return range_query(1, 1, n, pos, pos);
}

void make_table() {
	for(int i=1; i<=n; i++) table[0][i]= par[i]!=0 ? par[i] : -1 ;
	for(int i=1; i<19; i++) {
		for(int j=1; j<=n; j++) {
			int md=table[i-1][j];
			if(md!=-1) {
				table[i][j]=table[i-1][md];
			}
		}
	}
}

int BS(int x) {
	int lo=1, hi=n; int middle=(hi+lo)>>1;
	int ans=0;
	while(lo<=hi) {
		int ret=range_query(1, 1, n, 1, middle);
		ret=middle-ret;
		if(ret>=x) ans=middle, hi=middle-1;
		else lo=middle+1;
		middle=(hi+lo)>>1;
	}
	return ans;
}

int BruteForceRangeUpdate(int x) {
	int c=0; int upto=0;
	for(int i=1; i<=n; i++) {
		if(auxilary[i]==0) c++;
		if(c==x) { upto=i; break; }
	}
	for(int i=1; i<=upto; i++) {
		auxilary[i]=1;
	}
	return upto;
}

void BruteForceRemove(int x) {
	auxilary[x]=0;
}

int lift_it(int x) {
	for(int i=18; i>=0; i--) {
		if(table[i][x]!=-1) {
			//int ret=single_query_BruteForce(where[table[i][x]]);
			int ret=auxilary[where[table[i][x]]];
			if(ret==1) x=table[i][x];
		}
	}
	return x;
}

int main () {
	cin>>n>>Q; memset(table, -1, sizeof(table));
	for(int i=1; i<=n; i++) {
		cin>>par[i]; if(par[i]==0) root=i;
		v[par[i]].push_back(i);
	}
	dfs(root); make_arr(root);
	make_table(); calc_depth(root, 1);
	for(int i=1; i<=Q; i++) {
		int op, x; cin>>op>>x;
		if(op==1) {
			//int temp=BS(x);
			int temp=BruteForceRangeUpdate(x);
			cout<<a[temp]<<endl;
			//update(1, 1, n, 1, temp);
		}
		else {
			int temp=lift_it(x);
			cout<<depth[x]-depth[temp]<<endl;
			BruteForceRemove(where[temp]);
			//remove(1, 1, n, where[temp]);
		}
	}
	//system("pause");

	return 0;
}

Subtask #1
3.84615384615 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 16088 KB Output isn't correct
2 Runtime error 316 ms 17144 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 213 ms 17144 KB Execution timed out (wall clock limit exceeded)
4 Incorrect 0 ms 16088 KB Output isn't correct
5 Incorrect 0 ms 16088 KB Output isn't correct
6 Correct 0 ms 16088 KB Output is correct
7 Correct 6 ms 16088 KB Output is correct
8 Incorrect 0 ms 16088 KB Output isn't correct
9 Incorrect 16 ms 16220 KB Output isn't correct
10 Incorrect 76 ms 16352 KB Output isn't correct
11 Runtime error 293 ms 17144 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 176 ms 17144 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 319 ms 17144 KB Execution timed out (wall clock limit exceeded)

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 153 ms 18488 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 543 ms 23800 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 206 ms 18496 KB Execution timed out (wall clock limit exceeded)
4 Incorrect 336 ms 18400 KB Output isn't correct
5 Incorrect 389 ms 18388 KB Output isn't correct
6 Incorrect 436 ms 18396 KB Output isn't correct
7 Runtime error 366 ms 17384 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 159 ms 18488 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 596 ms 23808 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 443 ms 23804 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 453 ms 23804 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 439 ms 20744 KB Execution timed out (wall clock limit exceeded)
13 Incorrect 276 ms 28388 KB Output isn't correct
14 Incorrect 226 ms 18496 KB Output isn't correct

Subtask #3
17.1428571429 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 19884 KB Output is correct
2 Correct 576 ms 20940 KB Output is correct
3 Correct 476 ms 27224 KB Output is correct
4 Runtime error 379 ms 22316 KB Execution timed out (wall clock limit exceeded)
5 Correct 326 ms 22320 KB Output is correct
6 Correct 403 ms 22316 KB Output is correct
7 Correct 363 ms 19864 KB Output is correct
8 Runtime error 379 ms 27216 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 446 ms 23808 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 523 ms 23812 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 526 ms 23804 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 433 ms 20944 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 573 ms 30064 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 286 ms 18500 KB Execution timed out (wall clock limit exceeded)

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 563 ms 23812 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 579 ms 20944 KB Execution timed out (wall clock limit exceeded)
3 Incorrect 323 ms 30072 KB Output isn't correct
4 Runtime error 483 ms 23808 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 519 ms 23808 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 499 ms 23808 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 606 ms 20944 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 436 ms 30068 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 196 ms 18500 KB Execution timed out (wall clock limit exceeded)