oj.uz

답안 #107252

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107252 2019-04-23T01:06:13 Z wilwxk Ball Machine (BOI13_ballmachine) C++11
4.95726 / 100
 1000 ms 19200 KB 
#include <bits/stdc++.h>
using namespace std;

struct node {
	int mn, mni, cnt;
};

const int MAXN=1e5+5;
vector<int> g[MAXN], ord;
set<int> s;
node seg[MAXN*4];
int indt[MAXN], prof[MAXN];
int n, q;

void dfs(int cur, int p) {
	for(auto viz : g[cur]) {
		if(viz==p) continue;
		prof[viz]=prof[cur]+1;
		dfs(viz, cur);
	}
	ord.push_back(cur);
	indt[cur]=ord.size()-1;
}

int query(int sind, int ini, int fim, int qini, int qfim) {
	if(qini>fim||qfim<ini) return 0;
	if(qini<=ini&&qfim>=fim) return seg[sind].mni;
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	int aa=query(e, ini, m, qini, qfim);
	int bb=query(d, m+1, fim, qini, qfim);
	if(prof[ord[aa]]<=prof[ord[bb]]) return aa;
	else return bb;
}

void update(int sind, int ini, int fim, int qind, int k) {
	if(qind<ini||qind>fim) return;
	if(ini==fim) {
		if(k==1) seg[sind].mn=prof[ord[ini]], seg[sind].cnt=0;
		else seg[sind].mn=MAXN, seg[sind].cnt=1;
		return;
	}
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	update(e, ini, m, qind, k); update(d, m+1, fim, qind, k);

	seg[sind].mn=min(seg[e].mn, seg[d].mn);
	if(seg[sind].mn==seg[e].mn) seg[sind].mni=seg[e].mni;
	else seg[sind].mni=seg[d].mni;
	seg[sind].cnt=seg[e].cnt+seg[d].cnt;
}

void build(int sind, int ini, int fim) {
	if(ini==fim) {
		seg[sind].mn=MAXN;
		seg[sind].mni=ini;
		seg[sind].cnt=1;
		return;
	}
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	build(e, ini, m); build(d, m+1, fim);
	seg[sind].mn=MAXN; seg[sind].mni=0;
	seg[sind].cnt=seg[e].cnt+seg[d].cnt;
}

int main() {
	scanf("%d %d", &n, &q);
	for(int i=1; i<=n; i++) {
		int a; scanf("%d", &a);
		if(a==0) continue;
		g[a].push_back(i); g[i].push_back(a);
	}

	for(int i=1; i<=n; i++) sort(g[i].begin(), g[i].end());
	ord.push_back(0); prof[1]=1; dfs(1, 1); prof[0]=MAXN;
	for(int i=1; i<=n; i++) s.insert(i);

	build(1, 1, n);

	while(q--) {
		int a, val; scanf("%d %d", &a, &val);
		if(a==1) {
			int ind;
			for(int i=1; i<=val; i++) {
				ind=*s.begin();
				update(1, 1, n, ind, 1);
				s.erase(s.begin());
				// printf("%d > %d // %d\n", i, ind, ord[query(1, 1, n, 1, n)]);
			}
			printf("%d\n", ord[ind]);
		}
		else {
			int cara=query(1, 1, n, indt[val], n);
			// printf("qu %d %d > %d\n", indt[val], n, ord[cara]);
			printf("%d\n", prof[val]-prof[ord[cara]]);
			update(1, 1, n, cara, -1);
			s.insert(cara);
		}

	}
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:67:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a; scanf("%d", &a);
          ~~~~~^~~~~~~~~~
ballmachine.cpp:79:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, val; scanf("%d %d", &a, &val);
               ~~~~~^~~~~~~~~~~~~~~~~~~
ballmachine.cpp:88:26: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
    printf("%d\n", ord[ind]);
                          ^

Subtask #1
3.84615384615 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1067 ms 2688 KB Time limit exceeded
2 Execution timed out 1075 ms 10232 KB Time limit exceeded
3 Correct 137 ms 10488 KB Output is correct
4 Execution timed out 1072 ms 2688 KB Time limit exceeded
5 Execution timed out 1090 ms 2688 KB Time limit exceeded
6 Incorrect 5 ms 2816 KB Output isn't correct
7 Execution timed out 1087 ms 2816 KB Time limit exceeded
8 Incorrect 7 ms 2816 KB Output isn't correct
9 Execution timed out 1052 ms 3200 KB Time limit exceeded
10 Execution timed out 1080 ms 4608 KB Time limit exceeded
11 Execution timed out 1083 ms 10232 KB Time limit exceeded
12 Correct 116 ms 10596 KB Output is correct
13 Incorrect 177 ms 10300 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 6228 KB Output isn't correct
2 Execution timed out 1068 ms 16456 KB Time limit exceeded
3 Incorrect 165 ms 15340 KB Output isn't correct
4 Execution timed out 1068 ms 6912 KB Time limit exceeded
5 Execution timed out 1074 ms 6904 KB Time limit exceeded
6 Execution timed out 1067 ms 6904 KB Time limit exceeded
7 Execution timed out 1081 ms 6524 KB Time limit exceeded
8 Incorrect 93 ms 6084 KB Output isn't correct
9 Execution timed out 1074 ms 17408 KB Time limit exceeded
10 Execution timed out 1052 ms 16624 KB Time limit exceeded
11 Incorrect 297 ms 16800 KB Output isn't correct
12 Incorrect 316 ms 16752 KB Output isn't correct
13 Incorrect 155 ms 17220 KB Output isn't correct
14 Incorrect 151 ms 15344 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 177 ms 9884 KB Output isn't correct
2 Incorrect 380 ms 16880 KB Output isn't correct
3 Incorrect 236 ms 16116 KB Output isn't correct
4 Incorrect 198 ms 15216 KB Output isn't correct
5 Incorrect 203 ms 14744 KB Output isn't correct
6 Incorrect 182 ms 14960 KB Output isn't correct
7 Incorrect 199 ms 14328 KB Output isn't correct
8 Incorrect 194 ms 15984 KB Output isn't correct
9 Incorrect 355 ms 17724 KB Output isn't correct
10 Incorrect 320 ms 16752 KB Output isn't correct
11 Incorrect 264 ms 17236 KB Output isn't correct
12 Incorrect 345 ms 16884 KB Output isn't correct
13 Incorrect 249 ms 19200 KB Output isn't correct
14 Incorrect 299 ms 15128 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1057 ms 17712 KB Time limit exceeded
2 Incorrect 273 ms 16508 KB Output isn't correct
3 Correct 201 ms 18536 KB Output is correct
4 Execution timed out 1080 ms 17692 KB Time limit exceeded
5 Incorrect 249 ms 16632 KB Output isn't correct
6 Incorrect 202 ms 16888 KB Output isn't correct
7 Incorrect 307 ms 16500 KB Output isn't correct
8 Correct 188 ms 18640 KB Output is correct
9 Incorrect 174 ms 15468 KB Output isn't correct