제출 #107481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107481		wilwxk	Ball Machine (BOI13_ballmachine)	C++11	16.23 / 100	269 ms	16912 KiB

ballmachine

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

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

const int MAXN=1e5+10;
vector<int> g[MAXN], ord;
priority_queue<int> pq;
node seg[MAXN*4];
int indt[MAXN], prof[MAXN];
int menor[MAXN];
int n, q, raiz;

bool cmp(int a, int b) {
	return menor[a]<menor[b];
}

void predfs(int cur) {
	menor[cur]=cur;
	for(auto viz : g[cur]) {
		predfs(viz);
		menor[cur]=min(menor[cur], menor[viz]);
	}
}
void dfs(int cur) {
	for(auto viz : g[cur]) {
		prof[viz]=prof[cur]+1;
		dfs(viz);
	}
	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].cnt=seg[e].cnt+seg[d].cnt;
	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;
}


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) raiz=i;
		g[a].push_back(i);
	}

	predfs(raiz);
	for(int i=1; i<=n; i++) sort(g[i].begin(), g[i].end(), cmp);
	ord.push_back(0); prof[raiz]=1; dfs(raiz); prof[0]=MAXN;
	for(int i=1; i<=n; i++) pq.push(-i);

	build(1, 1, n);

	while(q--) {
		int a, val; scanf("%d %d", &a, &val);
		if(a==1) {
			int ind=0;
			for(int i=1; i<=val; i++) {
				ind=-pq.top();
				update(1, 1, n, ind, 1);
				pq.pop();
				// 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);
			pq.push(-cara);
			// printf("qu %d %d > %d\n", indt[val], n, ord[cara]);
		}

	}
}

컴파일 시 표준 에러 (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:92: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);
               ~~~~~^~~~~~~~~~~~~~~~~~~

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