oj.uz

답안 #107253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107253 2019-04-23T01:15:00 Z wilwxk Ball Machine (BOI13_ballmachine) C++11
0 / 100
 1000 ms 19320 KB 
#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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 2688 KB Output isn't correct
2 Execution timed out 1080 ms 10464 KB Time limit exceeded
3 Execution timed out 1067 ms 10268 KB Time limit exceeded
4 Execution timed out 1087 ms 2688 KB Time limit exceeded
5 Incorrect 5 ms 2688 KB Output isn't correct
6 Incorrect 5 ms 2816 KB Output isn't correct
7 Execution timed out 1072 ms 2816 KB Time limit exceeded
8 Incorrect 7 ms 2816 KB Output isn't correct
9 Execution timed out 1092 ms 3200 KB Time limit exceeded
10 Incorrect 378 ms 4736 KB Output isn't correct
11 Execution timed out 1082 ms 10632 KB Time limit exceeded
12 Execution timed out 1091 ms 10232 KB Time limit exceeded
13 Execution timed out 1085 ms 10260 KB Time limit exceeded

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 893 ms 6100 KB Output isn't correct
2 Execution timed out 1087 ms 16860 KB Time limit exceeded
3 Incorrect 123 ms 15472 KB Output isn't correct
4 Execution timed out 1083 ms 7160 KB Time limit exceeded
5 Execution timed out 1085 ms 7032 KB Time limit exceeded
6 Execution timed out 1079 ms 7248 KB Time limit exceeded
7 Execution timed out 1093 ms 6528 KB Time limit exceeded
8 Execution timed out 1018 ms 6268 KB Time limit exceeded
9 Execution timed out 1093 ms 17580 KB Time limit exceeded
10 Execution timed out 1083 ms 16616 KB Time limit exceeded
11 Execution timed out 1094 ms 16628 KB Time limit exceeded
12 Execution timed out 1082 ms 16624 KB Time limit exceeded
13 Execution timed out 1088 ms 17244 KB Time limit exceeded
14 Incorrect 124 ms 15472 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1087 ms 9980 KB Time limit exceeded
2 Execution timed out 1081 ms 16792 KB Time limit exceeded
3 Execution timed out 1077 ms 16376 KB Time limit exceeded
4 Execution timed out 1075 ms 15376 KB Time limit exceeded
5 Execution timed out 1087 ms 14788 KB Time limit exceeded
6 Execution timed out 1083 ms 15104 KB Time limit exceeded
7 Execution timed out 1086 ms 14484 KB Time limit exceeded
8 Execution timed out 1084 ms 16244 KB Time limit exceeded
9 Execution timed out 1074 ms 17864 KB Time limit exceeded
10 Execution timed out 1085 ms 16688 KB Time limit exceeded
11 Execution timed out 1075 ms 17268 KB Time limit exceeded
12 Execution timed out 1055 ms 16916 KB Time limit exceeded
13 Execution timed out 1085 ms 19320 KB Time limit exceeded
14 Execution timed out 1074 ms 15524 KB Time limit exceeded

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1074 ms 17708 KB Time limit exceeded
2 Execution timed out 1059 ms 16576 KB Time limit exceeded
3 Execution timed out 1083 ms 18512 KB Time limit exceeded
4 Execution timed out 1081 ms 17800 KB Time limit exceeded
5 Execution timed out 1081 ms 16472 KB Time limit exceeded
6 Execution timed out 1083 ms 16932 KB Time limit exceeded
7 Execution timed out 1078 ms 16628 KB Time limit exceeded
8 Execution timed out 1061 ms 18520 KB Time limit exceeded
9 Incorrect 123 ms 15600 KB Output isn't correct