Submission #1187376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187376		8pete8	The Ties That Guide Us (CEOI23_incursion)	C++20	100 / 100	148 ms	6040 KiB

incursion

#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)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&=((n-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]=pa[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]=pa[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];
  else pa[have[0]]=0;
  while(t==0){
    cur=pa[cur];
    t=visit(cur);
  }
  vector<pii>choice;
  while(1){
    choice.clear();
    for(auto i:adj[cur]){
      if(i!=pa[cur])choice.pb({sz[i],i});
    }
    sort(rall(choice));
    int yes=1;
    for(auto i:choice){
      t=visit(i.s);
      if(t){
        cur=i.s;
        yes=0;
        break;
      }
      else t=visit(cur);
    }
    if(yes)return;
  }
}

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:49:40: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   49 | vector<int> mark(vector<pii>F, int safe){
      |                                        ^
incursion.cpp:63:42: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   63 | void locate(vector<pii>F, int curr, int t){
      |                                          ^

• Subtask 0: 0 / 0
• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40