#include "incursion.h"
#include <bits/stdc++.h>
using namespace std;
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
int n;
vector<vector<int>> adj;
vector<int> sub, prt;
ii root = {-1, -1};
int Visit(int u){ return visit(u + 1); }
void getSub(int u, int p)
{
sub[u] = 1;
for (const auto v : adj[u])
{
if (v == p) continue;
getSub(v, u);
sub[u] += sub[v];
}
}
bool iscentroid(int u)
{
if (2 * (n - sub[u]) > n) return false;
for (const auto& v : adj[u])
{
if (v == prt[u]) continue;
if (2 * sub[v] > n) return false;
}
return true;
}
bool isRoot(int u)
{
assert(u != -1);
return root.F == u || root.S == u;
}
void getPrt(int u, int p)
{
prt[u] = p;
for (const auto v : adj[u])
{
if (v == p) continue;
getPrt(v, u);
}
}
void getRoot()
{
sub.resize(n);
getSub(0, -1);
getPrt(0, -1);
int u = 0;
while (!iscentroid(u))
{
for (const auto v : adj[u])
{
if (v == prt[u]) continue;
if (2 * sub[v] > n)
{
u = v;
break;
}
}
}
root.F = u;
for (const auto v : adj[u])
{
if (iscentroid(v)) root.S = v;
}
}
vector<int> mark(vector<pair<int, int>> edges, int safe)
{
n = sz(edges) + 1;
adj.resize(n); prt.resize(n);
safe--;
for (auto& [u, v] : edges) { u--; v--; }
for (auto [u, v] : edges)
{
adj[u].pb(v);
adj[v].pb(u);
}
getRoot();
getPrt(root.F, -1);
int u = safe;
vector<int> res(n, 0);
while (!isRoot(u))
{
res[u] = 1;
u = prt[u];
}
res[u] = 1;
return res;
}
void locate(vector<pair<int, int>> edges, int src, int tcnt)
{
n = sz(edges) + 1;
adj.resize(n);
src--;
for (auto& [u, v] : edges) { u--; v--; }
for (auto [u, v] : edges)
{
adj[u].pb(v);
adj[v].pb(u);
}
getRoot();
getPrt(root.F, -1);
getSub(root.F, -1);
bool vst[n]{};
int u = src;
vst[u] = 1;
while (!isRoot(u) && tcnt == 0)
{
u = prt[u];
tcnt = Visit(u);
vst[u] = 1;
}
if (tcnt == 0) // go to other root
{
u = (u == root.F ? root.S : root.F);
tcnt = Visit(u);
vst[u] = 1;
assert(tcnt > 0);
}
while (true)
{
vector<int> nxt;
for (const auto v : adj[u])
{
if (vst[v] || v == prt[u]) continue;
nxt.pb(v);
}
sort(all(nxt), [](int v1, int v2){ return sub[v1] > sub[v2]; });
assert(sz(nxt) <= 2);
bool found = 0;
for (const auto v : nxt)
{
tcnt = Visit(v);
if (tcnt == 1)
{
found = 1;
u = v;
break;
}
tcnt = Visit(u);
}
if (!found) return;
}
}
Compilation message
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);
| ~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
768 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
83 ms |
16464 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
11092 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
768 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
