Submission #107250

#	Time	Username	Problem	Language	Result	Execution time	Memory
107250		wilwxk	Ball Machine (BOI13_ballmachine)	C++11	4.96 / 100	240 ms	14292 KiB

ballmachine

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

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

const int MAXN=1e5+5;
vector<int> g[MAXN], ord;
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;

	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=query2(1, 1, n, 1);
				update(1, 1, n, ind, 1);
				// 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, cara);
			// printf("%d\n", prof[val]-prof[ord[cara]]);
			printf("0\n");
			update(1, 1, n, indt[val], -1);
		}

	}
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:71: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:73: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:84: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:92:26: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
    printf("%d\n", ord[ind]);
                          ^

• Subtask 1: 3.8461538461538463 / 25
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.1111111111111112 / 5