#include "incursion.h"
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
ll sub[50000];
vector<ll> edges[50000];
ll par[50000];
ll visited[50000];
ll depth[50000];
ll unsure[50000];
ll n;
void dfs(ll a, ll p, ll d){
depth[a] = d;
par[a] = p;
sub[a] = 1;
for (auto&i : edges[a]){
if (i != p) dfs(i,a,d+1), sub[a] += sub[i];
}
}
ll centfind(ll a, ll p){
for (auto&i : edges[a]){
if (i!=p && sub[i] > n/2) return centfind(i, a);
}
return a;
}
vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
n = F.size()+1;
vector<int> ties(F.size()+1);
FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0;
for (auto&i : F){
edges[i.first].push_back(i.second);
edges[i.second].push_back(i.first);
}
dfs(1, -1, 0);
ll cent = centfind(1, -1);
dfs(cent, -1, 0);
while (safe != -1){
ties[safe-1] = 1;
safe = par[safe];
}
return ties;
}
bool cmp(ll a, ll b){
return sub[a] < sub[b];
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
n = F.size()+1;
vector<int> ties(F.size()+1);
FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0;
for (auto&i : F){
edges[i.first].push_back(i.second);
edges[i.second].push_back(i.first);
}
dfs(1, -1, 0);
ll cent = centfind(1, -1);
dfs(cent, -1, 0);
visited[curr] = 1;
while (t != 1 && curr != cent){
t = visit(par[curr]);
curr = par[curr];
visited[curr] = 1;
}
while (1){
if (t==0 && curr!=cent){
t = visit(par[curr]);
curr = par[curr];
}
sort(edges[curr].begin(), edges[curr].end(), cmp);
reverse(edges[curr].begin(), edges[curr].end());
bool done = false;
for (auto&i : edges[curr]){
if (i==par[curr]) continue;
if (!visited[i]){
visited[i] = true;
t = visit(i);
curr = i;
done = true;
break;
}
}
if (!done){
if (curr != cent && visited[par[curr]] == 0){
t = visit(par[curr]);
visited[par[curr]] = 1;
curr = par[curr];
}else{
return;
}
}
}
}
Compilation message
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/vector:60,
from incursion.h:1,
from incursion.cpp:2:
/usr/include/c++/10/type_traits: In substitution of 'template<class _Fn, class ... _Args> using invoke_result_t = typename std::invoke_result::type [with _Fn = long long int&; _Args = {}]':
/usr/include/c++/10/variant:1705:13: required from 'constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...) [with _Visitor = long long int&; _Variants = {}]'
incursion.cpp:91:28: required from here
/usr/include/c++/10/type_traits:2957:11: error: no type named 'type' in 'struct std::invoke_result<long long int&>'
2957 | using invoke_result_t = typename invoke_result<_Fn, _Args...>::type;
| ^~~~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:133,
from incursion.cpp:4:
/usr/include/c++/10/variant: In instantiation of 'constexpr decltype(auto) std::visit(_Visitor&&, _Variants&& ...) [with _Visitor = long long int&; _Variants = {}]':
incursion.cpp:91:28: required from here
/usr/include/c++/10/variant:1708:13: error: no type named 'type' in 'struct std::invoke_result<long long int&>'
1708 | using _Tag = __detail::__variant::__deduce_visit_result<_Result_type>;
| ^~~~
interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
50 | int l = (numbers.size() == N ? N : 0);
| ~~~~~~~~~~~~~~~^~~~
