/*
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>
#include "incursion.h"
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
vector<int> mark(vector<pii> edg, int safe) {
int n= edg.size()+1;
safe--;
vector<int> sbt(n,1),p(n);
vector<vector<int>> g(n);
for(pii& a:edg)
g[--a.ff].push_back(--a.ss),g[a.ss].push_back(a.ff);
function<void(int,int)> dfs = [&](int cur,int prev)
{
p[cur] = prev;
for(int a : g[cur])
{
if(a==prev)continue;
dfs(a,cur);
sbt[cur]+=sbt[a];
}
};
dfs(safe,safe);
vector<int>res(n,0);
for(int i = 0; i < n; i++)
if(i!=safe)
{
int mx = 0;
for(int j : g[i])
if(j!=p[i])
mx = max(mx,sbt[j]);
if(n-sbt[i] >= mx)
res[i] = 1;
}
return res;
}
void locate(vector<pii> edg, int curr, int t) {
int n = edg.size()+1;
curr--;
vector<int> sbt(n,1),p(n);
vector<vector<int>> g(n);
for(pii &a:edg)
g[--a.ff].push_back(--a.ss),g[a.ss].push_back(a.ff);
function<void(int,int)> dfs = [&](int cur,int prev)
{
p[cur] = prev;
for(int a : g[cur])
{
if(a==prev)continue;
dfs(a,cur);
sbt[cur]+=sbt[a];
}
};
dfs(curr,curr);
vector<vector<int>> did(n);
for(int i = 0; i< n; i++)
did[i].resize(g[i].size(),0);
function<int(int,int)> gt = [&](int cur,int nxt)
{
if(nxt==p[cur])
return n-sbt[cur];
return sbt[nxt];
};
vector<int> vis(n,-1);
vis[curr]= t;
while(1)
{
vector<int> cons;
for(int i = 0; i < g[curr].size();i++)
cons.push_back(i);
sort(cons.begin(),cons.end(),[&](int a,int b)
{return gt(curr,g[curr][a])>gt(curr,g[curr][b]);});
int bn = 0;
for(int j = 0; j < g[curr].size();j++)
bn+=1-did[curr][j];
if(bn==0 && !t)
return;
int idx = 0;
if(t==1)
{
while(idx<g[curr].size()&&did[curr][cons[idx]]&>(curr,g[curr][cons[idx]])==gt(curr,g[curr][cons[0]]))
idx++;
if(idx==g[curr].size()||gt(curr,g[curr][cons[idx]])!=gt(curr,g[curr][cons[0]]))
idx--;
}
else{
while(idx<g[curr].size()&&
(did[curr][cons[idx]]||gt(curr,g[curr][cons[idx]])==gt(curr,g[curr][cons[0]])))
idx++;
if(idx==g[curr].size())return;
}
did[curr][cons[idx]] = 1;
curr = g[curr][cons[idx]];
t = visit(curr+1);
}
}
