oj.uz

답안 #107250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107250 2019-04-23T00:54:00 Z wilwxk Ball Machine (BOI13_ballmachine) C++11
4.95726 / 100
 240 ms 14292 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].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

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2688 KB Output isn't correct
2 Incorrect 122 ms 7520 KB Output isn't correct
3 Correct 80 ms 7544 KB Output is correct
4 Incorrect 4 ms 2688 KB Output isn't correct
5 Incorrect 4 ms 2688 KB Output isn't correct
6 Incorrect 6 ms 2816 KB Output isn't correct
7 Incorrect 6 ms 2816 KB Output isn't correct
8 Incorrect 5 ms 2788 KB Output isn't correct
9 Incorrect 10 ms 2944 KB Output isn't correct
10 Incorrect 31 ms 3840 KB Output isn't correct
11 Incorrect 159 ms 7292 KB Output isn't correct
12 Correct 151 ms 7700 KB Output is correct
13 Incorrect 130 ms 7352 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 5368 KB Output isn't correct
2 Incorrect 188 ms 11888 KB Output isn't correct
3 Incorrect 112 ms 10956 KB Output isn't correct
4 Incorrect 76 ms 5752 KB Output isn't correct
5 Incorrect 88 ms 5632 KB Output isn't correct
6 Incorrect 65 ms 5752 KB Output isn't correct
7 Incorrect 82 ms 5400 KB Output isn't correct
8 Incorrect 46 ms 5368 KB Output isn't correct
9 Incorrect 161 ms 12808 KB Output isn't correct
10 Incorrect 158 ms 11892 KB Output isn't correct
11 Incorrect 144 ms 12036 KB Output isn't correct
12 Incorrect 203 ms 12336 KB Output isn't correct
13 Incorrect 150 ms 13172 KB Output isn't correct
14 Incorrect 130 ms 10864 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 90 ms 7560 KB Output isn't correct
2 Incorrect 197 ms 11888 KB Output isn't correct
3 Incorrect 143 ms 12344 KB Output isn't correct
4 Incorrect 147 ms 11504 KB Output isn't correct
5 Incorrect 112 ms 10736 KB Output isn't correct
6 Incorrect 145 ms 11244 KB Output isn't correct
7 Incorrect 133 ms 10728 KB Output isn't correct
8 Incorrect 124 ms 12268 KB Output isn't correct
9 Incorrect 199 ms 12908 KB Output isn't correct
10 Incorrect 189 ms 11820 KB Output isn't correct
11 Incorrect 164 ms 12404 KB Output isn't correct
12 Incorrect 199 ms 11936 KB Output isn't correct
13 Incorrect 189 ms 14292 KB Output isn't correct
14 Incorrect 173 ms 10736 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 240 ms 12784 KB Output isn't correct
2 Incorrect 216 ms 11892 KB Output isn't correct
3 Correct 150 ms 14012 KB Output is correct
4 Incorrect 154 ms 12784 KB Output isn't correct
5 Incorrect 168 ms 11760 KB Output isn't correct
6 Incorrect 161 ms 12148 KB Output isn't correct
7 Incorrect 178 ms 11760 KB Output isn't correct
8 Correct 119 ms 13940 KB Output is correct
9 Incorrect 94 ms 10864 KB Output isn't correct