oj.uz

답안 #107247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107247 2019-04-23T00:43:16 Z wilwxk Ball Machine (BOI13_ballmachine) C++11
4.95726 / 100
 295 ms 15860 KB 
#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].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]]);
			update(1, 1, n, cara, -1);
		}

	}
}

Compilation message

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

Subtask #1
3.84615384615 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2688 KB Output isn't correct
2 Incorrect 191 ms 8516 KB Output isn't correct
3 Correct 82 ms 8568 KB Output is correct
4 Incorrect 4 ms 2688 KB Output isn't correct
5 Incorrect 5 ms 2688 KB Output isn't correct
6 Incorrect 6 ms 2816 KB Output isn't correct
7 Incorrect 5 ms 2688 KB Output isn't correct
8 Incorrect 7 ms 2816 KB Output isn't correct
9 Incorrect 11 ms 3072 KB Output isn't correct
10 Incorrect 36 ms 4096 KB Output isn't correct
11 Incorrect 179 ms 8568 KB Output isn't correct
12 Correct 134 ms 8596 KB Output is correct
13 Incorrect 168 ms 8492 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 5964 KB Output isn't correct
2 Incorrect 269 ms 13424 KB Output isn't correct
3 Incorrect 111 ms 11888 KB Output isn't correct
4 Incorrect 104 ms 6648 KB Output isn't correct
5 Incorrect 115 ms 6520 KB Output isn't correct
6 Incorrect 113 ms 6628 KB Output isn't correct
7 Incorrect 106 ms 6264 KB Output isn't correct
8 Incorrect 49 ms 6008 KB Output isn't correct
9 Incorrect 180 ms 14316 KB Output isn't correct
10 Incorrect 185 ms 13480 KB Output isn't correct
11 Incorrect 190 ms 13556 KB Output isn't correct
12 Incorrect 217 ms 13780 KB Output isn't correct
13 Incorrect 155 ms 14220 KB Output isn't correct
14 Incorrect 116 ms 11884 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 119 ms 8332 KB Output isn't correct
2 Incorrect 242 ms 13672 KB Output isn't correct
3 Incorrect 178 ms 13252 KB Output isn't correct
4 Incorrect 156 ms 12508 KB Output isn't correct
5 Incorrect 170 ms 11888 KB Output isn't correct
6 Incorrect 152 ms 12272 KB Output isn't correct
7 Incorrect 175 ms 11676 KB Output isn't correct
8 Incorrect 120 ms 13268 KB Output isn't correct
9 Incorrect 265 ms 14284 KB Output isn't correct
10 Incorrect 256 ms 13428 KB Output isn't correct
11 Incorrect 219 ms 14004 KB Output isn't correct
12 Incorrect 189 ms 13552 KB Output isn't correct
13 Incorrect 195 ms 15860 KB Output isn't correct
14 Incorrect 200 ms 12100 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 287 ms 14420 KB Output isn't correct
2 Incorrect 227 ms 13260 KB Output isn't correct
3 Correct 157 ms 15228 KB Output is correct
4 Incorrect 295 ms 14320 KB Output isn't correct
5 Incorrect 232 ms 13376 KB Output isn't correct
6 Incorrect 291 ms 13812 KB Output isn't correct
7 Incorrect 221 ms 13308 KB Output isn't correct
8 Correct 128 ms 15092 KB Output is correct
9 Incorrect 109 ms 12016 KB Output isn't correct