Submission #107251

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
107251	2019-04-23T01:04:50 Z	wilwxk	Ball Machine (BOI13_ballmachine)	C++11	4.95726 / 100	1000 ms	23908 KB

ballmachine

#include <bits/stdc++.h>
using namespace std;

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

const int MAXN=3e5+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;
}

int query2(int sind, int ini, int fim, int val) {
	if(ini==fim) return fim;
	int m=(ini+fim)/2; int e=sind*2; int d=e+1;
	if(seg[e].cnt>=val) return query2(e, ini, m, val);
	else return query2(d, m+1, fim, val-seg[e].cnt);
}

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:72: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:74: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:86: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:95:26: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
    printf("%d\n", ord[ind]);
                          ^

Subtask #1

3.84615384615 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1074 ms	7424 KB	Time limit exceeded
2	Execution timed out	1067 ms	14972 KB	Time limit exceeded
3	Correct	102 ms	15224 KB	Output is correct
4	Execution timed out	1077 ms	7424 KB	Time limit exceeded
5	Execution timed out	1078 ms	7424 KB	Time limit exceeded
6	Incorrect	11 ms	7552 KB	Output isn't correct
7	Execution timed out	1082 ms	7552 KB	Time limit exceeded
8	Incorrect	11 ms	7552 KB	Output isn't correct
9	Execution timed out	1069 ms	7808 KB	Time limit exceeded
10	Execution timed out	1069 ms	9340 KB	Time limit exceeded
11	Execution timed out	1058 ms	15128 KB	Time limit exceeded
12	Correct	112 ms	15224 KB	Output is correct
13	Incorrect	190 ms	15068 KB	Output isn't correct

Subtask #2

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	63 ms	10872 KB	Output isn't correct
2	Execution timed out	1069 ms	21364 KB	Time limit exceeded
3	Incorrect	174 ms	20084 KB	Output isn't correct
4	Execution timed out	1083 ms	11640 KB	Time limit exceeded
5	Execution timed out	1083 ms	11640 KB	Time limit exceeded
6	Execution timed out	1080 ms	11648 KB	Time limit exceeded
7	Execution timed out	1068 ms	11136 KB	Time limit exceeded
8	Incorrect	65 ms	11000 KB	Output isn't correct
9	Execution timed out	1072 ms	21972 KB	Time limit exceeded
10	Execution timed out	1077 ms	21236 KB	Time limit exceeded
11	Incorrect	206 ms	21492 KB	Output isn't correct
12	Incorrect	260 ms	21532 KB	Output isn't correct
13	Incorrect	173 ms	22048 KB	Output isn't correct
14	Incorrect	176 ms	20020 KB	Output isn't correct

Subtask #3

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	177 ms	14532 KB	Output isn't correct
2	Incorrect	324 ms	21484 KB	Output isn't correct
3	Incorrect	215 ms	20720 KB	Output isn't correct
4	Incorrect	240 ms	20016 KB	Output isn't correct
5	Incorrect	265 ms	19184 KB	Output isn't correct
6	Incorrect	284 ms	19720 KB	Output isn't correct
7	Incorrect	216 ms	19056 KB	Output isn't correct
8	Incorrect	254 ms	20720 KB	Output isn't correct
9	Incorrect	420 ms	22332 KB	Output isn't correct
10	Incorrect	283 ms	21456 KB	Output isn't correct
11	Incorrect	278 ms	22004 KB	Output isn't correct
12	Incorrect	278 ms	21564 KB	Output isn't correct
13	Incorrect	260 ms	23908 KB	Output isn't correct
14	Incorrect	361 ms	20012 KB	Output isn't correct

Subtask #4

1.11111111111 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1077 ms	22256 KB	Time limit exceeded
2	Incorrect	369 ms	21236 KB	Output isn't correct
3	Correct	176 ms	23328 KB	Output is correct
4	Execution timed out	1085 ms	22356 KB	Time limit exceeded
5	Incorrect	276 ms	21364 KB	Output isn't correct
6	Incorrect	260 ms	21620 KB	Output isn't correct
7	Incorrect	316 ms	21236 KB	Output isn't correct
8	Correct	158 ms	23272 KB	Output is correct
9	Incorrect	167 ms	20080 KB	Output isn't correct