#include<bits/stdc++.h>
#include "incursion.h"
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
const int mxn=5e4;
vector<int>adj[mxn];
int sz[mxn],target,val[mxn],pa[mxn],n;
int root[mxn];
void getsz(int cur,int p){
sz[cur]=1;for(auto i:adj[cur])if(i!=p&&root[i]==0){
pa[i]=cur;
getsz(i,cur),sz[cur]+=sz[i];
}
}
vector<int>have;
bool find(int cur,int p){
val[cur]=0;
if(cur==target)return val[cur]=1;
for(auto i:adj[cur])if(i!=p&&root[i]==0){
val[cur]|=find(i,cur);
}
return val[cur];
}
void getroot(){
getsz(1,-1);
for(int i=1;i<=n;i++){
int yes=1;
for(auto j:adj[i])if(j!=pa[i])yes&=(sz[j]<=(n)/2);
if(i!=1)yes&=((sz[1]-sz[i])<=((n)/2));
if(yes)have.pb(i);
}
if(have.size()>2||have.empty())assert(0);
for(auto i:have)root[i]=1;
for(auto i:have)find(i,-1);
}
vector<int> mark(vector<pii>F, int safe){
n=F.size()+1;
have.clear();
for(int i=1;i<=n;i++)adj[i].clear(),val[i]=root[i]=0;
for(auto i:F){
adj[i.f].pb(i.s);
adj[i.s].pb(i.f);
}
target=safe;
getroot();
vector<int>ans;
for(int i=1;i<=n;i++)ans.pb(val[i]);
return ans;
}
void locate(vector<pii>F, int curr, int t){
n=F.size()+1;
int cur=curr;
have.clear();
for(int i=1;i<=n;i++)adj[i].clear(),val[i]=root[i]=0;
for(auto i:F){
adj[i.f].pb(i.s);
adj[i.s].pb(i.f);
}
for(int i=1;i<=n;i++)if(adj[i].empty())assert(0);
getroot();
for(auto i:have)getsz(i,-1);
if(have.size()>1)pa[have[0]]=have[1],pa[have[1]]=have[0];
while(t==0){
cur=pa[cur];
if(cur==0)assert(0);
t=visit(cur);
}
if(cur==0||t==0)assert(0);
vector<int>choice;
while(1){
choice.clear();
for(auto i:adj[cur]){
if(i!=pa[cur])choice.pb(i);
}
if(choice.size()>1&&sz[choice[0]]<sz[choice[1]]){
swap(choice[0],choice[1]);
}
if(choice.empty())return;
t=visit(choice[0]);
if(t){
cur=choice[0];
}
else{
visit(cur);
if(choice.size()>1&&(!visit(choice[1])))return void(visit(cur));
cur=choice[1];
}
}
}
Compilation message (stderr)
incursion.cpp:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
16 | #pragma GCC optimize ("03,unroll-lopps")
| ^
incursion.cpp:22:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
22 | void getsz(int cur,int p){
| ^
incursion.cpp:29:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
29 | bool find(int cur,int p){
| ^
incursion.cpp:37:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
37 | void getroot(){
| ^
incursion.cpp:50:40: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
50 | vector<int> mark(vector<pii>F, int safe){
| ^
incursion.cpp:64:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
64 | void locate(vector<pii>F, int curr, int t){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |