oj.uz

Submission #110491

# Submission time Handle Problem Language Result Execution time Memory
110491 2019-05-11T00:22:01 Z wilwxk Ball Machine (BOI13_ballmachine) C++11
20.9524 / 100
 1000 ms 20840 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
const int LOGN=22;
vector<int> g[MAXN];
int dp[MAXN][LOGN];
int prof[MAXN], gin[MAXN];
int marc[MAXN];
set<int> s;
int n, q, root;
int contv;

void dfs(int cur, int p) {
	for(auto viz : g[cur]) {
		if(viz==p) continue;
		dp[viz][0]=cur;
		gin[cur]++;
		prof[viz]=prof[cur]+1;
		dfs(viz, cur);
	}
}

int pula(int cur) {
	for(int i=LOGN-1; i>=0; i--) {
		if(marc[dp[cur][i]]) cur=dp[cur][i];
	}
	return cur;
}

int main() {
	scanf("%d %d", &n, &q);
	for(int i=1; i<=n; i++) {
		int a; scanf("%d", &a);
		if(a==0) root=i;
		else g[a].push_back(i), g[i].push_back(a);
	}

	dfs(root, root);
	for(int i=1; i<=n; i++) if(!gin[i]) s.insert(i);
	for(int i=1; i<LOGN; i++) {
		for(int j=1; j<=n; j++) dp[j][i]=dp[dp[j][i-1]][i-1];
	}

	while(q--) {
		int a, x; scanf("%d %d", &a, &x);
		if(a==1) {
			int cur, p;
			while(x--) {
				cur= *s.begin();
				p=dp[cur][0];
				s.erase(s.begin());
				marc[cur]=1;
				gin[p]--;
				if(!gin[p]) s.insert(p);
			}
			printf("%d\n", cur);
		}
		else {
			int cur=pula(x);
			int p=dp[cur][0];
			marc[cur]=0;
			gin[p]++;
			s.erase(p);
			s.insert(cur);
			printf("%d\n", prof[x]-prof[cur]);
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:32: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:34: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:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, x; scanf("%d %d", &a, &x);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 2688 KB Time limit exceeded
2 Execution timed out 1072 ms 12868 KB Time limit exceeded
3 Incorrect 87 ms 12920 KB Output isn't correct
4 Execution timed out 1048 ms 2688 KB Time limit exceeded
5 Execution timed out 1078 ms 2688 KB Time limit exceeded
6 Incorrect 6 ms 2944 KB Output isn't correct
7 Execution timed out 1075 ms 2816 KB Time limit exceeded
8 Execution timed out 1075 ms 2816 KB Time limit exceeded
9 Execution timed out 1067 ms 3328 KB Time limit exceeded
10 Execution timed out 1079 ms 5240 KB Time limit exceeded
11 Execution timed out 1082 ms 12836 KB Time limit exceeded
12 Incorrect 103 ms 12920 KB Output isn't correct
13 Incorrect 182 ms 12808 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 6352 KB Output is correct
2 Execution timed out 1075 ms 19704 KB Time limit exceeded
3 Correct 166 ms 18420 KB Output is correct
4 Execution timed out 1083 ms 7680 KB Time limit exceeded
5 Execution timed out 1073 ms 7800 KB Time limit exceeded
6 Execution timed out 1088 ms 7808 KB Time limit exceeded
7 Execution timed out 1090 ms 7040 KB Time limit exceeded
8 Correct 43 ms 6520 KB Output is correct
9 Execution timed out 1083 ms 19292 KB Time limit exceeded
10 Execution timed out 1064 ms 19868 KB Time limit exceeded
11 Execution timed out 1073 ms 19832 KB Time limit exceeded
12 Execution timed out 1044 ms 18492 KB Time limit exceeded
13 Correct 119 ms 18352 KB Output is correct
14 Correct 120 ms 18420 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 11136 KB Output isn't correct
2 Incorrect 259 ms 18936 KB Output isn't correct
3 Correct 149 ms 17144 KB Output is correct
4 Incorrect 165 ms 16120 KB Output isn't correct
5 Incorrect 210 ms 16688 KB Output isn't correct
6 Incorrect 212 ms 16540 KB Output isn't correct
7 Incorrect 209 ms 15480 KB Output isn't correct
8 Correct 173 ms 17240 KB Output is correct
9 Incorrect 315 ms 19752 KB Output isn't correct
10 Incorrect 321 ms 20092 KB Output isn't correct
11 Incorrect 327 ms 20316 KB Output isn't correct
12 Incorrect 349 ms 18908 KB Output isn't correct
13 Correct 265 ms 20840 KB Output is correct
14 Incorrect 262 ms 18932 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 19192 KB Time limit exceeded
2 Incorrect 351 ms 18868 KB Output isn't correct
3 Correct 135 ms 20216 KB Output is correct
4 Execution timed out 1073 ms 19164 KB Time limit exceeded
5 Execution timed out 1072 ms 19772 KB Time limit exceeded
6 Execution timed out 1077 ms 19832 KB Time limit exceeded
7 Incorrect 323 ms 18808 KB Output isn't correct
8 Correct 158 ms 20344 KB Output is correct
9 Correct 128 ms 18548 KB Output is correct