QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #448715 | #8806. Summer Driving | Qwerty1232 | Compile Error | / | / | C++23 | 9.4kb | 2024-06-20 00:15:18 | 2024-06-20 00:15:19 |
Judging History
answer
#include <bits/stdc++.h>
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, start, a, b;
std::cin >> n >> start >> a >> b;
start--;
std::vector<std::vector<int>> gr(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
std::cin >> u >> v;
u--;
v--;
gr[u].push_back(v);
gr[v].push_back(u);
}
if (a <= b) {
std::cout << 1 << "\n";
return 0;
}
std::vector<int> depth(n), height(n), prv(n); //, max_sb(n);
{
auto dfs = [&](auto dfs, int v, int f) -> void {
prv[v] = f;
depth[v] = f == -1 ? 0 : depth[f] + 1;
height[v] = 0;
for (int& t : gr[v]) {
if (t != f) {
dfs(dfs, t, v);
height[v] = std::max(height[v], height[t] + 1);
} else {
t = -1;
}
}
std::erase(gr[v], -1);
};
dfs(dfs, start, -1);
}
std::vector<int> ord(n);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return height[a] < height[b]; });
// // dp1 - Alice, dp2 - Bob, dp3 - Alice restricted
std::vector<int> dp1(n, -1), dp2(n, n);
std::vector<std::vector<int>> dp3(n);
for (int i = 0; i < n; i++) {
dp3[i].assign(gr[i].size(), -1);
}
for (int i : ord) {
int g = gr[i].size();
{
auto dfs0 = [&](auto dfs0, int v, int f, int d) -> int {
if (d < 0) {
return n;
}
int val = v;
for (int t : gr[v]) {
if (t != f) {
val = std::min(val, dfs0(dfs0, t, v, d - 1));
}
}
return val;
};
auto dfs1 = [&](auto dfs1, int v, int f, int d) -> int {
if (d == 0) {
return v;
}
int val = -1;
for (int t : gr[v]) {
if (t != f) {
val = std::max(val, dfs1(dfs1, t, v, d - 1));
}
}
return val;
};
if (height[i] < a) {
dp1[i] = dfs0(dfs0, i, prv[i], b);
} else {
dp1[i] = dfs1(dfs1, i, prv[i], a);
}
dp1[i] = dfs1(dfs1, i, prv[i], b);
for (int j = 0; j < g; j++) {
int t = gr[i][j];
dp3[i][j] = dfs1(dfs1, t, i, a - 1);
if (dp3[i][j] == -1) {
dp3[i][j] = dfs0(dfs0, t, i, b - 1);
}
}
}
{
auto dfs = [&](auto dfs, int v, int f, int d, int val) {
if (d < 0) {
return;
}
dp2[v] = std::min(dp2[v], val);
for (int t : gr[v]) {
if (t != f) {
dfs(dfs, t, v, d - 1, val);
}
}
if (prv[i] != -1 && prv[i] != f) {
dfs(dfs, prv[i], v, d - 1, val);
}
};
dp2[i] = std::min(dp2[i], dp1[i]);
if (prv[i] != -1)
dfs(dfs, prv[i], i, b - 1, dp1[i]);
for (int j = 0; j < g; j++) {
int t = gr[i][j];
dfs(dfs, t, i, b - 1, dp3[i][j]);
}
}
}
std::cout << dp1[start] << "\n";
return 0;
}
#include <bits/stdc++.h>
int32_t main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, start, a, b;
std::cin >> n >> start >> a >> b;
start--;
std::vector<std::vector<int>> gr(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
std::cin >> u >> v;
u--;
v--;
gr[u].push_back(v);
gr[v].push_back(u);
}
if (a <= b) {
std::cout << 1 << "\n";
return 0;
}
std::vector<int> depth(n), height(n), prv(n); //, max_sb(n);
std::vector<int> jmp_a(n, -1);
{
std::vector<int> stack;
auto dfs = [&](auto dfs, int v, int f) -> void {
stack.push_back(v);
prv[v] = f;
depth[v] = f == -1 ? 0 : depth[f] + 1;
height[v] = 0;
// max_sb[v] = v;
for (int t : gr[v]) {
if (t != f) {
dfs(dfs, t, v);
height[v] = std::max(height[v], height[t] + 1);
// max_sb[v] = std::max(max_sb[v], max_sb[t]);
}
}
stack.pop_back();
};
dfs(dfs, start, -1);
}
std::vector<int> ord(n);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&](int a, int b) { return height[a] < height[b]; });
auto dfs_cum = [&](auto dfs_cum, int v, int f, int d) -> int {
if (d == 0) {
return v;
}
int res = v;
for (int t : gr[v]) {
if (t != f) {
res = std::min(res, dfs_cum(dfs_cum, t, v, d - 1));
}
}
return res;
};
std::vector<int> dp1(n, -1), dp2(n, n); // dp1 - Alice, dp2 - Bob
for (int i : ord) {
int g = gr[i].size();
std::vector<int> dp1_vec(g, -1);
if (height[i] < a) {
dp1[i] = dfs_cum(dfs_cum, i, prv[i], b);
for (int j = 0; j < g; j++) {
int t = gr[i][j];
if (t == prv[i]) {
continue;
}
dp1_vec[j] = dfs_cum(dfs_cum, t, i, b - 1);
}
int min = -1, min2 = -1;
min = i;
for (int j = 0; j < g; j++) {
int t = gr[i][j];
if (t == prv[i]) {
continue;
}
if (min > dp1_vec[j]) {
min2 = min;
min = dp1_vec[j];
} else {
min2 = std::min(min2, dp1_vec[j]);
}
}
{
auto dfs = [&](auto dfs, int v, int f, int d, int val) -> void {
if (d < 0) {
return;
}
dp2[v] = std::min(dp2[v], val);
for (int t : gr[v]) {
if (t != f) {
dfs(dfs, t, v, d - 1, val);
}
}
};
dp2[i] = std::min(dp2[i], min);
for (int j = 0; j < g; j++) {
int t = gr[i][j];
if (t == prv[i]) {
dfs(dfs, t, i, b - 1, min);
continue;
}
dfs(dfs, t, i, b - 1, dp1_vec[j] == min ? min2 : min);
}
}
} else {
dp1_vec.assign(g, -1);
for (int j = 0; j < g; j++) {
int t = gr[i][j];
if (t == prv[i]) {
continue;
}
auto dfs = [&](auto dfs, int v, int f, int d) -> void {
if (d == 0) {
dp1_vec[j] = dp2[v];
return;
}
for (int t : gr[v]) {
if (t != f) {
dfs(dfs, t, v, d - 1);
}
}
};
if (height[t] < a - 1) {
dp1_vec[j] = dfs_cum(dfs_cum, t, i, b - 1);
} else {
dfs(dfs, t, i, a - 1);
}
}
int max = -1, max2 = -1;
for (int j = 0; j < g; j++) {
int t = gr[i][j];
if (t == prv[i]) {
continue;
}
if (max < dp1_vec[j]) {
max2 = max;
max = dp1_vec[j];
} else {
max2 = std::max(max2, dp1_vec[j]);
}
}
if (max2 == -1) {
max2 = i;
}
dp1[i] = std::max(dp1[i], max);
{
auto dfs = [&](auto dfs, int v, int f, int d, int val) -> void {
assert(val != -1);
if (d < 0) {
return;
}
dp2[v] = std::min(dp2[v], val);
for (int t : gr[v]) {
if (t != f) {
dfs(dfs, t, v, d - 1, t == prv[v] ? val : max);
}
}
};
dp2[i] = std::min(dp2[i], max);
for (int j = 0; j < g; j++) {
int t = gr[i][j];
if (t == prv[i]) {
dfs(dfs, t, i, b - 1, max);
continue;
}
dfs(dfs, t, i, b - 1, dp1_vec[j] == max ? max2 : max);
}
}
}
}
std::cout << dp1[start] + 1 << "\n";
return 0;
}
Details
answer.code:129:9: error: redefinition of ‘int32_t main()’
129 | int32_t main() {
| ^~~~
answer.code:3:9: note: ‘int32_t main()’ previously defined here
3 | int32_t main() {
| ^~~~
In file included from /usr/include/c++/13/bits/stl_algobase.h:71,
from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from answer.code:1:
/usr/include/c++/13/bits/predefined_ops.h:195:9: error: mangling of ‘constexpr bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Value = int; _Compare = main()::<lambda(int, int)>]’ as ‘_ZN9__gnu_cxx5__ops14_Iter_comp_valIZ4mainEUliiE_EclINS_17__normal_iteratorIPiSt6vectorIiSaIiEEEEiEEbT_RT0_’ conflicts with a previous mangle
195 | operator()(_Iterator __it, _Value& __val)
| ^~~~~~~~
/usr/include/c++/13/bits/predefined_ops.h:195:9: note: previous mangling ‘constexpr bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Value = int; _Compare = main()::<lambda(int, int)>]’
/usr/include/c++/13/bits/predefined_ops.h:195:9: note: a later ‘-fabi-version=’ (or =0) avoids this error with a change in mangling
In file included from /usr/include/c++/13/bits/stl_algo.h:61,
from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_heap.h:135:5: error: mangling of ‘constexpr void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<main()::<lambda(int, int)> >]’ as ‘_ZSt11__push_heapIN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEEliNS0_5__ops14_Iter_comp_valIZ4mainEUliiE_EEEvT_T0_SC_T1_RT2_’ conflicts with a previous mangle
135 | __push_heap(_RandomAccessIterator __first,
| ^~~~~~~~~~~
/usr/include/c++/13/bits/stl_heap.h:135:5: note: previous mangling ‘constexpr void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<main()::<lambda(int, int)> >]’
/usr/include/c++/13/bits/stl_heap.h:135:5: note: a later ‘-fabi-version=’ (or =0) avoids this error with a change in mangling
/usr/include/c++/13/bits/stl_heap.h:224:5: error: mangling of ‘constexpr void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]’ as ‘_ZSt13__adjust_heapIN9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEEliNS0_5__ops15_Iter_comp_iterIZ4mainEUliiE_EEEvT_T0_SC_T1_T2_’ conflicts with a previous mangle
224 | __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
| ^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_heap.h:224:5: note: previous mangling ‘constexpr void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(int, int)> >]’
/usr/include/c++/13/bits/stl_heap.h:224:5: note: a later ‘-fabi-version=’ (or =0) avoids this error with a change in mangling
/usr/include/c++/13/bits/predefined_ops.h:187:7: error: mangling of ‘constexpr __gnu_cxx::__ops::_Iter_comp_val<_Compare>::_Iter_comp_val(__gnu_cxx::__ops::_Iter_comp_iter<_Compare>&&) [with _Compare = main()::<lambda(int, int)>]’ as ‘_ZN9__gnu_cxx5__ops14_Iter_comp_valIZ4mainEUliiE_EC1EONS0_15_Iter_comp_iterIS2_EE’ conflicts with a previous mangle
187 | _Iter_comp_val(_Iter_comp_iter<_Compare>&& __comp)
| ^~~~~~~~~~~~~~
/usr/include/c++/13/bits/predefined_ops.h:187:7: note: previous mangling ‘constexpr __gnu_cxx::__ops::_Iter_comp_val<_Compare>::_Iter_comp_val(__gnu_cxx::__ops::_Iter_comp_iter<_Compare>&&) [with _Compare = main()::<lambda(int, int)>]’
/usr/include/c++/13/bits/predefined_ops.h:187:7: note: a later ‘-fabi-version=’ (or =0) avoids this error with a change in mangling
/usr/include/c++/13/bits/predefined_ops.h:187:7: error: mangling of ‘constexpr __gnu_cxx::__ops::_Iter_comp_val<_Compare>::_Iter_comp_val(__gnu_cxx::__ops::_Iter_comp_iter<_Compare>&&) [with _Compare = main()::<lambda(int, int)>]’ as ‘_ZN9__gnu_cxx5__ops14_Iter_comp_valIZ4mainEUliiE_EC2EONS0_15_Iter_comp_iterIS2_EE’ conflicts with a previous mangle
/usr/include/c++/13/bits/predefined_ops.h:187:7: note: previous mangling ‘constexpr __gnu_cxx::__ops::_Iter_comp_val<_Compare>::_Iter_comp_val(__gnu_cxx::__ops:...