Submission #107253

#	Time	Username	Problem	Language	Result	Execution time	Memory
107253		wilwxk	Ball Machine (BOI13_ballmachine)	C++11	0 / 100	1094 ms	19320 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;
set<int> s;
node seg[MAXN*4];
int indt[MAXN], prof[MAXN];
int v[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;
// }

int query(int sind, int ini, int fim, int qini, int qfim) {
	int resp=qini;
	for(int i=qini; i<=qfim; i++) if(prof[ord[v[i]]]<prof[ord[v[resp]]]) resp=i;
	return resp; 
}

void update(int sind, int ini, int fim, int qind, int k) {
	if(k==1) v[qind]=qind;
	else v[qind]=0;
}

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("%d\n", prof[val]-prof[ord[cara]]);
			update(1, 1, n, cara, -1);
			s.insert(cara);
			// printf("qu %d %d > %d\n", indt[val], n, ord[cara]);
		}

	}
}

Compilation message (stderr)

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

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