/*
SAMPLE GRADER for task INCURSION
USAGE:
place together with your solution and incursion.h in the same directory, then:
g++ <flags> sample_grader.cpp <solution_file>
e.g.:
g++ -std=c++17 sample_grader.cpp incursion.cpp
INPUT/OUTPUT:
The sample grader first expects on standard input the integers N and safe.
Afterwards, it expects the floor plan F as a sequence of N-1 pairs of integers
1 <= u, v <= N (u != v).
It will then call mark(F, safe) and write its return value T to standard output.
After this, it expects your starting location curr and will call
locate(F, curr, T[curr-1]); note that the sample grader will not change the
numbering of rooms and doors. It will then write to standard output a protocol
of all calls to visit by your program.
Upon termination, the sample grader writes your verdict to standard output.
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#ifndef rtgsp
#include "incursion.h"
#endif // rtgsp
#ifdef rtgsp
namespace sample_grader {
constexpr int tieLimit = 1000000000;
int N;
int dest;
int curr;
vector<int> T;
vector<pair<int, int>> F;
enum { MARK, LOCATE } phase;
[[noreturn]] void die(const char *const s) {
cout << s << endl;
exit(0);
}
void print_vector(vector<int> v)
{
cout << "{";
for (size_t i = 0; i < v.size(); ++i) {
cout << v[i];
if (i + 1 != v.size()) cout << ", ";
}
cout << "}";
}
void print_vector(vector<pair<int, int>> v)
{
cout << "{";
for (size_t i = 0; i < v.size(); ++i) {
cout << "{" << v[i].first << ", " << v[i].second << "}";
if (i + 1 != v.size()) cout << ", ";
}
cout << "}";
}
} // namespace sample_grader
int visit(int v) {
using namespace sample_grader;
function<void()> die_invalid_call_to_visit = [&]() {
cout << "visit(" << v << ")" << endl;
die("Invalid call to visit");
};
if (phase == MARK || v < 1 || v > N) die_invalid_call_to_visit();
bool adjacent = false;
for (auto e : F) {
if (e == make_pair(v, curr) or e == make_pair(curr, v)) {
adjacent = true;
}
}
if (not adjacent) die_invalid_call_to_visit();
curr = v;
cout << "visit(" << v << ") returned " << T[v - 1] << endl;
return T[v - 1];
}
#endif // rtgsp
const int maxn = 5e4 + 2;
vector<int> child[maxn], adj[maxn];
int n, par[maxn], sz[maxn], d[maxn];
void dfs (int u, int p)
{
sz[u] = 1;
for (int v : adj[u])
{
if (v == p)
{
par[u] = v;
continue;
}
d[v] = d[u] + 1;
dfs(v, u);
sz[u] += sz[v];
child[u].push_back(v);
}
}
vector<int> ties;
vector<int> mark (vector<pair<int, int>> E, int safe)
{
n = E.size() + 1;
for (int i = 1; i <= n; i++)
{
adj[i].clear();
child[i].clear();
par[i] = d[i] = sz[i] = 0;
}
ties.resize(n, 0);
for (pair<int, int> p : E)
{
assert(p.first > 0 && p.second > 0);
adj[p.first].push_back(p.second);
adj[p.second].push_back(p.first);
}
dfs(safe, 0);
int c1 = -1, c2 = -1;
for (int u = 1; u <= n; u++)
{
bool check = true;
for (int v : child[u])
{
if (sz[v] > n/2)
{
check = false;
break;
}
}
if (n - sz[u] > n/2) check = false;
if (check)
{
if (c1 == -1) c1 = u;
else c2 = u;
}
}
int r = -1;
if (c2 == -1 || d[c1] < d[c2]) r = c1;
else r = c2;
while (r != safe)
{
ties[r - 1] = 1;
r = par[r];
}
ties[r - 1] = 1;
return ties;
}
bool cmp (int x, int y)
{
return sz[x] > sz[y];
}
vector<int> path;
void locate (vector<pair<int, int>> E, int cur, int t)
{
n = E.size() + 1;
for (int i = 1; i <= n; i++)
{
adj[i].clear();
child[i].clear();
par[i] = d[i] = sz[i] = 0;
}
for (pair<int, int> p : E)
{
adj[p.first].push_back(p.second);
adj[p.second].push_back(p.first);
}
dfs(cur, 0);
int c1 = -1, c2 = -1;
for (int u = 1; u <= n; u++)
{
bool check = true;
for (int v : child[u])
{
if (sz[v] > n/2)
{
check = false;
break;
}
}
if (n - sz[u] > n/2) check = false;
if (check)
{
if (c1 == -1) c1 = u;
else c2 = u;
}
}
int r = -1, r2 = -1;
if (c2 == -1 || d[c1] > d[c2]) r = c1;
else r = c2;
r2 = r;
while (r2 != cur)
{
path.push_back(r2);
r2 = par[r2];
}
reverse(path.begin(), path.end());
for (int i = 1; i <= n; i++)
{
child[i].clear();
par[i] = d[i] = sz[i] = 0;
}
dfs(r, 0);
if (t == 0)
{
for (int u : path)
{
t = visit(u);
if (t == 1)
{
cur = u;
break;
}
}
if (cur != c1 && cur != c2) return;
}
for (int u = 1; u <= n; u++)
{
sort(child[u].begin(), child[u].end(), cmp);
}
while (true)
{
bool found = true;
for (int v : child[cur])
{
t = visit(v);
if (t == 0) visit(cur);
else
{
cur = v;
found = false;
break;
}
}
if (found) return;
}
}
#ifdef rtgsp
int main() {
using namespace sample_grader;
if (!(cin >> N >> dest) or N < 2 or dest < 1 or dest > N) die("Invalid input");
vector<int> deg(N + 1);
for(int i = 1; i < N; ++i) {
int u, v;
if (!(cin >> u >> v) or min(u, v) < 1 or max(u, v) > N or u == v) {
die("Invalid input");
}
F.emplace_back(u, v);
++deg[u]; ++deg[v];
if(deg[u] > 3 or deg[v] > 3) die("Invalid input");
}
vector<bool> visited(N + 1, false);
function<void(int)> visit = [&](int x) {
visited[x] = true;
for (auto [a, b] : F) {
if (b == x) swap(a, b);
if (a != x or visited[b]) continue;
visit(b);
}
};
visit(1);
if (not all_of(visited.begin() + 1, visited.end(), [](bool b) { return b; })) {
die("Invalid input");
}
phase = MARK;
T = mark(F, dest);
cout << "mark(";
print_vector(F);
cout << ", " << dest << ") returned ";
print_vector(T);
cout << endl;
if (T.size() != static_cast<size_t>(N)) die("Invalid return value of mark");
for (int x : T) {
if (x < 0 or x > tieLimit) die("Invalid return value of mark");
}
phase = LOCATE;
cout << "Enter curr: ";
if (!(cin >> curr) or curr < 1 or curr > N) die("Invalid input");
cout << "locate(";
print_vector(F);
cout << ", " << curr << ", " << T[curr - 1] << ")" << endl;
locate(F, curr, T[curr - 1]);
if (curr == dest) {
cout << "Correct: at most " << *max_element(T.begin(), T.end()) << " tie(s) per room" << endl;
} else {
cout << "Not correct: current position is " << curr << endl;
}
return 0;
}
#endif // rtgsp
