| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 872077 | vjudge1 | Ball Machine (BOI13_ballmachine) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
* IN THE NAME OF GOD */
// Oh, let the bullets fly, oh, let them rain
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100'000, lg = 18;
bool is_filled[MAXN + 10];
int par_sp[MAXN + 10][lg + 10], order[MAXN + 10], mn[MAXN + 10], par[MAXN + 10], n, q, tt;
vector<int> adj[MAXN + 10];
set<pair<int, int>> take_order;
void input();
void solve();
void dfs_get_minimum(int u, int par);
void dfs_get_order(int u, int par);
void par_spars_table();
int query1(int cnt);
int query2(int id);
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
input();
solve();
return 0;
}
void input() {
cin >> n >> q;
for (int i = 0; i < n; i++) {
cin >> par[i];
par[i]--;
if (par[i] == -1)
continue;
adj[par[i]].push_back(i);
adj[i].push_back(par[i]);
}
}
void solve() {
dfs_get_minimum(0, -1);
dfs_get_order(0, -1);
par_spars_table();
//cout << par_sp[7][2] << '\n';
for (int i = 0; i < n; i++)
take_order.insert({order[i], i});
while (q--) {
int type, x;
cin >> type >> x;
if (type == 1)
cout << query1(x) + 1 << '\n';
else {
x--;
cout << query2(x) << '\n';
}
}
}
void dfs_get_minimum(int u, int par) {
int res = u;
for (int v : adj[u])
if (v != par) {
dfs_get_minimum(v, u);
res = min(res, mn[v]);
}
mn[u] = res;
}
void dfs_get_order(int u, int par) {
set<pair<int, int>> st;
for (int v : adj[u])
if (v != par)
st.insert({mn[v], v});
for (auto p : st)
dfs_get_order(p.second, u);
order[u] = tt++;
}
void par_spars_table() {
for (int i = 0; i < n; i++)
par_sp[i][0] = par[i];
for (int k = 1; k < lg; k++)
for (int i = 0; i < n; i++) {
if (par_sp[i][k - 1] == -1)
par_sp[i][k] = -1;
else
par_sp[i][k] = par_sp[par_sp[i][k - 1]][k - 1];
}
}
int query1(int cnt) {
for (int i = 0; i < cnt; i++) {
int u = (*take_order.begin()).second;
is_filled[u] = true;
take_order.erase(take_order.begin());
if (i == cnt - 1)
return u;
}
}
int query2(int id) {
int u = id, ans = 0;
for (int k = lg - 1; k >= 0; k--) {
if (par_sp[u][k] == -1)
continue;
if (is_filled[par_sp[u][k]] == true) {
u = par_sp[u][k];
ans += (1 << k);
}
}
is_filled[u] = false;
take_order.insert({order[u], u});
return ans;
}
Compilation message (stderr)
ballmachine.cpp:1:19: error: expected constructor, destructor, or type conversion before 'THE'
1 | * IN THE NAME OF GOD */
| ^~~
In file included from /usr/include/c++/10/cmath:43,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/ext/type_traits.h:162:35: error: 'bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
162 | __is_null_pointer(std::nullptr_t)
| ^
/usr/include/c++/10/ext/type_traits.h:157:5: note: previous declaration 'template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)'
157 | __is_null_pointer(_Type)
| ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/type_traits.h:162:26: error: 'nullptr_t' is not a member of 'std'
162 | __is_null_pointer(std::nullptr_t)
| ^~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/type_traits:402:26: error: 'std::size_t' has not been declared
402 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/10/type_traits:403:25: error: '_Size' was not declared in this scope
403 | struct is_array<_Tp[_Size]>
| ^~~~~
/usr/include/c++/10/type_traits:403:31: error: template argument 1 is invalid
403 | struct is_array<_Tp[_Size]>
| ^
/usr/include/c++/10/type_traits:508:42: error: 'nullptr_t' is not a member of 'std'
508 | struct __is_null_pointer_helper<std::nullptr_t>
| ^~~~~~~~~
/usr/include/c++/10/type_traits:508:51: error: template argument 1 is invalid
508 | struct __is_null_pointer_helper<std::nullptr_t>
| ^
/usr/include/c++/10/type_traits:1351:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1351 | : public integral_constant<std::size_t, alignof(_Tp)>
| ^~~~~~
In file included from /usr/include/stdlib.h:31,
from /usr/include/c++/10/bits/std_abs.h:38,
from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/type_traits:1351:57: error: template argument 1 is invalid
1351 | : public integral_constant<std::size_t, alignof(_Tp)>
| ^
/usr/include/c++/10/type_traits:1351:57: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1360:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1360 | : public integral_constant<std::size_t, 0> { };
| ^~~~~~
In file included from /usr/include/stdlib.h:31,
from /usr/include/c++/10/bits/std_abs.h:38,
from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/type_traits:1360:46: error: template argument 1 is invalid
1360 | : public integral_constant<std::size_t, 0> { };
| ^
/usr/include/c++/10/type_traits:1360:46: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1362:26: error: 'std::size_t' has not been declared
1362 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/10/type_traits:1363:21: error: '_Size' was not declared in this scope
1363 | struct rank<_Tp[_Size]>
| ^~~~~
/usr/include/c++/10/type_traits:1363:27: error: template argument 1 is invalid
1363 | struct rank<_Tp[_Size]>
| ^
/usr/include/c++/10/type_traits:1364:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1364 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^~~~~~
In file included from /usr/include/stdlib.h:31,
from /usr/include/c++/10/bits/std_abs.h:38,
from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/type_traits:1364:65: error: template argument 1 is invalid
1364 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^
/usr/include/c++/10/type_traits:1364:65: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1368:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1368 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^~~~~~
In file included from /usr/include/stdlib.h:31,
from /usr/include/c++/10/bits/std_abs.h:38,
from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/type_traits:1368:65: error: template argument 1 is invalid
1368 | : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
| ^
/usr/include/c++/10/type_traits:1368:65: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1373:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1373 | : public integral_constant<std::size_t, 0> { };
| ^~~~~~
In file included from /usr/include/stdlib.h:31,
from /usr/include/c++/10/bits/std_abs.h:38,
from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/type_traits:1373:46: error: template argument 1 is invalid
1373 | : public integral_constant<std::size_t, 0> { };
| ^
/usr/include/c++/10/type_traits:1373:46: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1375:42: error: 'std::size_t' has not been declared
1375 | template<typename _Tp, unsigned _Uint, std::size_t _Size>
| ^~~
/usr/include/c++/10/type_traits:1376:23: error: '_Size' was not declared in this scope
1376 | struct extent<_Tp[_Size], _Uint>
| ^~~~~
/usr/include/c++/10/type_traits:1376:36: error: template argument 1 is invalid
1376 | struct extent<_Tp[_Size], _Uint>
| ^
/usr/include/c++/10/type_traits:1377:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1377 | : public integral_constant<std::size_t,
| ^~~~~~
In file included from /usr/include/stdlib.h:31,
from /usr/include/c++/10/bits/std_abs.h:38,
from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/type_traits:1378:24: error: '_Size' was not declared in this scope
1378 | _Uint == 0 ? _Size : extent<_Tp,
| ^~~~~
/usr/include/c++/10/type_traits:1379:28: error: template argument 1 is invalid
1379 | _Uint - 1>::value>
| ^
/usr/include/c++/10/type_traits:1379:28: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1384:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
1384 | : public integral_constant<std::size_t,
| ^~~~~~
In file included from /usr/include/stdlib.h:31,
from /usr/include/c++/10/bits/std_abs.h:38,
from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
209 | typedef __SIZE_TYPE__ size_t;
| ^~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/type_traits:1386:31: error: template argument 1 is invalid
1386 | _Uint - 1>::value>
| ^
/usr/include/c++/10/type_traits:1386:31: note: invalid template non-type parameter
/usr/include/c++/10/type_traits:1975:26: error: 'std::size_t' has not been declared
1975 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/10/type_traits:1976:30: error: '_Size' was not declared in this scope
1976 | struct remove_extent<_Tp[_Size]>
| ^~~~~
/usr/include/c++/10/type_traits:1976:36: error: template argument 1 is invalid
1976 | struct remove_extent<_Tp[_Size]>
| ^
/usr/include/c++/10/type_traits:1988:26: error: 'std::size_t' has not been declared
1988 | template<typename _Tp, std::size_t _Size>
| ^~~
/usr/include/c++/10/type_traits:1989:35: error: '_Size' was not declared in this scope
1989 | struct remove_all_extents<_Tp[_Size]>
| ^~~~~
/usr/include/c++/10/type_traits:1989:41: error: template argument 1 is invalid
1989 | struct remove_all_extents<_Tp[_Size]>
| ^
/usr/include/c++/10/type_traits:2047:12: error: 'std::size_t' has not been declared
2047 | template<std::size_t _Len>
| ^~~
/usr/include/c++/10/type_traits:2052:23: error: '_Len' was not declared in this scope
2052 | unsigned char __data[_Len];
| ^~~~
/usr/include/c++/10/type_traits:2067:12: error: 'std::size_t' has not been declared
2067 | template<std::size_t _Len, std::size_t _Align =
| ^~~
/usr/include/c++/10/type_traits:2067:30: error: 'std::size_t' has not been declared
2067 | template<std::size_t _Len, std::size_t _Align =
| ^~~
/usr/include/c++/10/type_traits:2068:48: error: '_Len' was not declared in this scope
2068 | __alignof__(typename __aligned_storage_msa<_Len>::__type)>
| ^~~~
/usr/include/c++/10/type_traits:2068:52: error: template argument 1 is invalid
2068 | __alignof__(typename __aligned_storage_msa<_Len>::__type)>
| ^
/usr/include/c++/10/type_traits:2073:23: error: '_Len' was not declared in this scope
2073 | unsigned char __data[_Len];
| ^~~~
/usr/include/c++/10/type_traits:2074:37: error: '_Align' was not declared in this scope
2074 | struct __attribute__((__aligned__((_Align)))) { } __align;
| ^~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:92:12: error: 'std::size_t' has not been declared
92 | template<std::size_t...>
| ^~~
/usr/include/c++/10/bits/stl_pair.h:449:36: error: 'std::size_t' has not been declared
449 | template<typename... _Args1, std::size_t... _Indexes1,
| ^~~
/usr/include/c++/10/bits/stl_pair.h:450:36: error: 'std::size_t' has not been declared
450 | typename... _Args2, std::size_t... _Indexes2>
| ^~~
/usr/include/c++/10/bits/stl_pair.h:453:27: error: '_Indexes1' was not declared in this scope
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:453:36: error: expected parameter pack before '...'
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^~~
/usr/include/c++/10/bits/stl_pair.h:453:39: error: template argument 1 is invalid
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^
/usr/include/c++/10/bits/stl_pair.h:453:55: error: '_Indexes2' was not declared in this scope
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:453:64: error: expected parameter pack before '...'
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^~~
/usr/include/c++/10/bits/stl_pair.h:453:67: error: template argument 1 is invalid
453 | _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>);
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:65,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/bits/stl_iterator_base_types.h:125:67: error: 'ptrdiff_t' does not name a type
125 | template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
| ^~~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:65,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/bits/stl_iterator_base_types.h:1:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
+++ |+#include <cstddef>
1 | // Types used in iterator implementation -*- C++ -*-
In file included from /usr/include/c++/10/bits/stl_algobase.h:65,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from ballmachine.cpp:3:
/usr/include/c++/10/bits/stl_iterator_base_types.h:214:15: error: 'ptrdiff_t' does not name a type
214 | typedef ptrdiff_t difference_type;
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_iterator_base_types.h:214:15: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
/usr/include/c++/10/bits/stl_iterato