oj.uz

Submission #107481

# Submission time Handle Problem Language Result Execution time Memory
107481 2019-04-24T17:31:19 Z wilwxk Ball Machine (BOI13_ballmachine) C++11
16.2271 / 100
 269 ms 16912 KB 
#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]);
		}

	}
}

Compilation message

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.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2688 KB Output isn't correct
2 Incorrect 162 ms 6920 KB Output isn't correct
3 Correct 74 ms 7028 KB Output is correct
4 Incorrect 5 ms 2688 KB Output isn't correct
5 Incorrect 5 ms 2688 KB Output isn't correct
6 Incorrect 6 ms 2836 KB Output isn't correct
7 Incorrect 7 ms 2816 KB Output isn't correct
8 Incorrect 5 ms 2688 KB Output isn't correct
9 Incorrect 14 ms 2988 KB Output isn't correct
10 Incorrect 39 ms 3712 KB Output isn't correct
11 Incorrect 185 ms 7668 KB Output isn't correct
12 Correct 87 ms 7028 KB Output is correct
13 Incorrect 140 ms 7636 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5752 KB Output is correct
2 Incorrect 219 ms 12668 KB Output isn't correct
3 Correct 97 ms 9456 KB Output is correct
4 Incorrect 123 ms 6336 KB Output isn't correct
5 Incorrect 115 ms 6288 KB Output isn't correct
6 Incorrect 88 ms 6136 KB Output isn't correct
7 Incorrect 119 ms 5720 KB Output isn't correct
8 Correct 45 ms 5624 KB Output is correct
9 Incorrect 246 ms 13292 KB Output isn't correct
10 Incorrect 239 ms 12656 KB Output isn't correct
11 Incorrect 213 ms 13200 KB Output isn't correct
12 Incorrect 269 ms 12080 KB Output isn't correct
13 Correct 165 ms 14956 KB Output is correct
14 Correct 105 ms 9452 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 8148 KB Output isn't correct
2 Incorrect 243 ms 12148 KB Output isn't correct
3 Incorrect 161 ms 14460 KB Output isn't correct
4 Incorrect 140 ms 11932 KB Output isn't correct
5 Incorrect 150 ms 11504 KB Output isn't correct
6 Incorrect 128 ms 11508 KB Output isn't correct
7 Incorrect 157 ms 10544 KB Output isn't correct
8 Incorrect 153 ms 14320 KB Output isn't correct
9 Incorrect 257 ms 13552 KB Output isn't correct
10 Incorrect 244 ms 13292 KB Output isn't correct
11 Incorrect 260 ms 13416 KB Output isn't correct
12 Incorrect 237 ms 12164 KB Output isn't correct
13 Incorrect 216 ms 16912 KB Output isn't correct
14 Incorrect 214 ms 10096 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 223 ms 13680 KB Output isn't correct
2 Incorrect 253 ms 12096 KB Output isn't correct
3 Correct 151 ms 16116 KB Output is correct
4 Incorrect 254 ms 13700 KB Output isn't correct
5 Incorrect 259 ms 12840 KB Output isn't correct
6 Incorrect 196 ms 12584 KB Output isn't correct
7 Incorrect 223 ms 12068 KB Output isn't correct
8 Correct 147 ms 16116 KB Output is correct
9 Correct 110 ms 9500 KB Output is correct