oj.uz

Submission #110692

# Submission time Handle Problem Language Result Execution time Memory
110692 2019-05-12T05:46:56 Z ckodser Ball Machine (BOI13_ballmachine) C++14
100 / 100
 403 ms 25436 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 100005, LG = 18;
int n, q, ts, P[N], H[N], rev[N], mn[N], par[N][LG], M[N];
vector < int > Adj[N];
set < int > S;
bool CMP(int i, int j)
{
	return (mn[i] < mn[j]);
}
void DFS(int v)
{
	mn[v] = v;
	for (int i = 1; i < LG; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	for (int &u : Adj[v])
	{
		H[u] = H[v] + 1;
		par[u][0] = v;
		DFS(u);
		mn[v] = min(mn[v], mn[u]);
	}
}
void DFS2(int v)
{
	for (int &u : Adj[v])
		DFS2(u);
	P[v] = ts ++;
	rev[P[v]] = v;
	S.insert(P[v]);
}
inline int Get(int v)
{
	for (int i = LG - 1; ~ i; i --)
		if (M[par[v][i]])
			v = par[v][i];
	return (v);
}
int main()
{
	scanf("%d%d", &n, &q);
	for (int i = 1, p; i <= n; i++)
		scanf("%d", &p), Adj[p].push_back(i);
	DFS(0);
	for (int i = 0; i <= n; i++)
		sort(Adj[i].begin(), Adj[i].end(), CMP);
	DFS2(0);
	for (; q; q --)
	{
		int tp, v;
		scanf("%d%d", &tp, &v);
		if (tp == 1)
		{
			int u;
			for (; v; v --)
			{
				u = rev[*S.begin()];
				S.erase(S.begin());
				M[u] = 1;
			}
			printf("%d\n", u);
		}
		else
		{
			int u = Get(v);
			M[u] = 0;
			S.insert(P[u]);
			printf("%d\n", H[v] - H[u]);
		}
	}
	return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:41: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:43:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p), Adj[p].push_back(i);
   ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &tp, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 251 ms 13432 KB Output is correct
3 Correct 99 ms 12792 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2816 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 12 ms 3328 KB Output is correct
10 Correct 45 ms 5240 KB Output is correct
11 Correct 282 ms 13608 KB Output is correct
12 Correct 109 ms 12920 KB Output is correct
13 Correct 174 ms 13044 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 6776 KB Output is correct
2 Correct 390 ms 21496 KB Output is correct
3 Correct 127 ms 17652 KB Output is correct
4 Correct 113 ms 8752 KB Output is correct
5 Correct 139 ms 8644 KB Output is correct
6 Correct 100 ms 8656 KB Output is correct
7 Correct 132 ms 8116 KB Output is correct
8 Correct 45 ms 6880 KB Output is correct
9 Correct 274 ms 21728 KB Output is correct
10 Correct 383 ms 21696 KB Output is correct
11 Correct 203 ms 21468 KB Output is correct
12 Correct 253 ms 19960 KB Output is correct
13 Correct 185 ms 22072 KB Output is correct
14 Correct 128 ms 17524 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 12280 KB Output is correct
2 Correct 376 ms 20448 KB Output is correct
3 Correct 271 ms 20288 KB Output is correct
4 Correct 237 ms 17916 KB Output is correct
5 Correct 220 ms 17660 KB Output is correct
6 Correct 213 ms 17656 KB Output is correct
7 Correct 230 ms 16576 KB Output is correct
8 Correct 227 ms 20344 KB Output is correct
9 Correct 363 ms 22168 KB Output is correct
10 Correct 302 ms 21696 KB Output is correct
11 Correct 302 ms 21680 KB Output is correct
12 Correct 321 ms 20472 KB Output is correct
13 Correct 345 ms 25436 KB Output is correct
14 Correct 252 ms 18624 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 22196 KB Output is correct
2 Correct 403 ms 20412 KB Output is correct
3 Correct 225 ms 24696 KB Output is correct
4 Correct 296 ms 22228 KB Output is correct
5 Correct 320 ms 21760 KB Output is correct
6 Correct 260 ms 20988 KB Output is correct
7 Correct 368 ms 20588 KB Output is correct
8 Correct 191 ms 24572 KB Output is correct
9 Correct 147 ms 17524 KB Output is correct