QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #733409 | #9570. Binary Tree | qinglu09 | Compile Error | / | / | C++23 | 7.1kb | 2024-11-10 18:42:29 | 2024-11-10 18:42:29 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int inf = 1E18;
int num=0;
int ask (int x, int y) {
cout << "? " << x << " " << y << endl;
int t;
cin >> t;
return t;
}
void Print (int x) {
cout << "! " << x << endl;
if(num==90)
{
cout << x << endl;
exit(0);
}
}
void solve () {
++num;
int n;
cin >> n;
vector <vector <int>> e (n + 1);
for (int i = 1; i <= n; i ++) {
int x, y;
cin >> x >> y;
if (x) {
e[x].push_back (i);
e[i].push_back (x);
}
if (y) {
e[y].push_back (i);
e[i].push_back (y);
}
}
vector <bool> ok (n + 1);
auto work = [&] (auto &&self, int x, int fa) -> void {
ok[x] = true;
for (auto y : e[x]) {
if (y == fa) {
continue;
}
if (ok[y]) {
continue;
}
self (self, y, x);
}
};
while (true) {
int rt;
int m = 0;
for (int i = 1; i <= n; i ++) {
if (! ok[i]) {
rt = i;
m ++;
}
}
int cent;
vector <int> sz (n + 1, 1);
vector <int> wt (n + 1);
auto dfs = [&] (auto &&self, int x, int fa) -> void {
for (auto y : e[x]) {
if (y == fa) {
continue;
}
if (ok[y]) {
continue;
}
self (self, y, x);
sz[x] += sz[y];
wt[x] = max (wt[x], sz[y]);
}
wt[x] = max (wt[x], m - sz[x]);
};
dfs (dfs, rt, -1);
for (int i = 1; i <= n; i ++) {
if (! ok[i] && wt[i] <= m / 2) {
cent = i;
break;
}
}
sz.assign (n + 1, 1);
vector <int> b;
for (auto y : e[cent]) {
if (! ok[y]) {
b.push_back (y);
}
}
if (b.size () == 3) {
for (int i = 0; i < 3; i ++) {
dfs (dfs, b[i], cent);
}
sort (b.begin (), b.end (),
[&] (const int &x, const int &y) {
return sz[x] > sz[y];
}
);
int t = ask (b[0], b[1]);
if (t == 0) {
work (work, cent, b[0]);
} else if (t == 1) {
work (work, b[0], cent);
work (work, b[1], cent);
} else {
work (work, cent, b[1]);
}
} else if (b.size () == 2) {
int t = ask (b[0], b[1]);
if (t == 0) {
work (work, cent, b[0]);
} else if (t == 1) {
Print (cent);
return;
} else {
work (work, cent, b[1]);
}
} else if (b.size () == 1) {
int t = ask (cent, b[0]);
if (t == 0) {
Print (cent);
} else {
Print (b[0]);
}
return;
} else {
Print (cent);
return;
}
}
}
signed main () {
ios::sync_with_stdio (false);
cin.tie (nullptr);
num++;
int T = 1;
cin >> T;
while (T --) {
solve ();
}
return 0;
}
#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int inf = 1E18;
int num=0;
int ask (int x, int y) {
cout << "? " << x << " " << y << endl;
int t;
cin >> t;
return t;
}
void Print (int x) {
cout << "! " << x << endl;
if(num==90)
{
cout << x << endl;
exit(0);
}
}
void solve () {
++num;
int n;
cin >> n;
vector <vector <int>> e (n + 1);
for (int i = 1; i <= n; i ++) {
int x, y;
cin >> x >> y;
if (x) {
e[x].push_back (i);
e[i].push_back (x);
}
if (y) {
e[y].push_back (i);
e[i].push_back (y);
}
}
vector <bool> ok (n + 1);
auto work = [&] (auto &&self, int x, int fa) -> void {
ok[x] = true;
for (auto y : e[x]) {
if (y == fa) {
continue;
}
if (ok[y]) {
continue;
}
self (self, y, x);
}
};
while (true) {
int rt;
int m = 0;
for (int i = 1; i <= n; i ++) {
if (! ok[i]) {
rt = i;
m ++;
}
}
int cent;
vector <int> sz (n + 1, 1);
vector <int> wt (n + 1);
auto dfs = [&] (auto &&self, int x, int fa) -> void {
for (auto y : e[x]) {
if (y == fa) {
continue;
}
if (ok[y]) {
continue;
}
self (self, y, x);
sz[x] += sz[y];
wt[x] = max (wt[x], sz[y]);
}
wt[x] = max (wt[x], m - sz[x]);
};
dfs (dfs, rt, -1);
for (int i = 1; i <= n; i ++) {
if (! ok[i] && wt[i] <= m / 2) {
cent = i;
break;
}
}
sz.assign (n + 1, 1);
vector <int> b;
for (auto y : e[cent]) {
if (! ok[y]) {
b.push_back (y);
}
}
if (b.size () == 3) {
for (int i = 0; i < 3; i ++) {
dfs (dfs, b[i], cent);
}
sort (b.begin (), b.end (),
[&] (const int &x, const int &y) {
return sz[x] > sz[y];
}
);
int t = ask (b[0], b[1]);
if (t == 0) {
work (work, cent, b[0]);
} else if (t == 1) {
work (work, b[0], cent);
work (work, b[1], cent);
} else {
work (work, cent, b[1]);
}
} else if (b.size () == 2) {
int t = ask (b[0], b[1]);
if (t == 0) {
work (work, cent, b[0]);
} else if (t == 1) {
Print (cent);
return;
} else {
work (work, cent, b[1]);
}
} else if (b.size () == 1) {
int t = ask (cent, b[0]);
if (t == 0) {
Print (cent);
} else {
Print (b[0]);
}
return;
} else {
Print (cent);
return;
}
}
}
signed main () {
ios::sync_with_stdio (false);
cin.tie (nullptr);
num++;
int T = 1;
cin >> T;
while (T --) {
solve ();
}
return 0;
}
Details
answer.code:166:15: error: redefinition of ‘constexpr const long long int inf’
166 | constexpr int inf = 1E18;
| ^~~
answer.code:6:15: note: ‘constexpr const long long int inf’ previously defined here
6 | constexpr int inf = 1E18;
| ^~~
answer.code:167:5: error: redefinition of ‘long long int num’
167 | int num=0;
| ^~~
answer.code:7:5: note: ‘long long int num’ previously defined here
7 | int num=0;
| ^~~
answer.code:168:5: error: redefinition of ‘long long int ask(long long int, long long int)’
168 | int ask (int x, int y) {
| ^~~
answer.code:8:5: note: ‘long long int ask(long long int, long long int)’ previously defined here
8 | int ask (int x, int y) {
| ^~~
answer.code:177:6: error: redefinition of ‘void Print(long long int)’
177 | void Print (int x) {
| ^~~~~
answer.code:17:6: note: ‘void Print(long long int)’ previously defined here
17 | void Print (int x) {
| ^~~~~
answer.code:188:6: error: redefinition of ‘void solve()’
188 | void solve () {
| ^~~~~
answer.code:28:6: note: ‘void solve()’ previously defined here
28 | void solve () {
| ^~~~~
answer.code:308:8: error: redefinition of ‘int main()’
308 | signed main () {
| ^~~~
answer.code:148:8: note: ‘int main()’ previously defined here
148 | signed 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<long long int*, std::vector<long long int> >; _Value = long long int; _Compare = solve()::<lambda(const long long int&, const long long int&)>]’ as ‘_ZN9__gnu_cxx5__ops14_Iter_comp_valIZ5solvevEUlRKxS3_E_EclINS_17__normal_iteratorIPxSt6vectorIxSaIxEEEExEEbT_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<long long int*, std::vector<long long int> >; _Value = long long int; _Compare = solve()::<lambda(const long long int&, const long long 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<long long int*, vector<long long int> >; _Distance = long int; _Tp = long long int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<solve()::<lambda(const long long int&, const long long int&)> >]’ as ‘_ZSt11__push_heapIN9__gnu_cxx17__normal_iteratorIPxSt6vectorIxSaIxEEEElxNS0_5__ops14_Iter_comp_valIZ5solvevEUlRKxSA_E_EEEvT_T0_SE_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<long long int*, vector<long long int> >; _Distance = long int; _Tp = long long int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<solve()::<lambda(const long long int&, const long long 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<long long int*, vector<long long int> >; _Distance = long int; _Tp = long long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<solve()::<lambda(const long long int&, const long long int&)> >]’ as ‘_ZSt13__adjust_heapIN9__gnu_cxx17__normal_iteratorIPxSt6vectorIxSaIxEEEElxNS0_5__ops15_Iter_comp_iterIZ5solvevEUlRKxSA_E_EEEvT_T0_SE_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<long long int*, vector<long ...