Submission #1239106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239106		noyancanturk	Werewolf (IOI18_werewolf)	C++20	0 / 100	313 ms	66684 KiB

werewolf

#include "werewolf.h"

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;

int n,m,q;

struct DSU{
  int*parent;
  DSU(){
    parent=new int[n];
    for(int i=0;i<n;i++){
      parent[i]=i;
    }
  }
  int find(int i){
    if(i==parent[i])return i;
    return parent[i]=find(parent[i]);
  }
  int unite(int i,int j){
    i=find(i),j=find(j);
    if(i==j)return 0;
    parent[j]=i;
    return 1;
  }
};

struct ST{
  int n,*tree;
  ST(int n):n(n),tree(new int[2*n+10]){
    for(int i=0;i<2*n+10;i++){
      tree[i]=-1;
    }
  }
  int query(int l,int r){
    int ans=-1;
    for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
      if(l&1){
        ans=max(ans,tree[l]);
        l++;
      }
      if(r&1){
        r--;
        ans=max(ans,tree[r]);
      }
    }
    return ans;
  }
  void update(int p,int val){
    p+=n;
    tree[p]=val;
    // cerr<<p<<'\n';
    for(p>>=1;p;p>>=1)tree[p]=max(tree[p<<1],tree[p<<1|1]);
  }
};

vector<int>v[lim];
vector<int>tree[lim];
int jump[20][lim];
vector<int>tour;
vector<int>tin,tout;

void dfs(int node){
  tin[node]=tour.size();
  tour.pb(node);
  for(int j:tree[node]){
    dfs(j);
  }
  tout[node]=tour.size()-1;
}

// state = 0 --> wolf ---- root = n-1
// state = 1 --> human ---- root = 0

array<vector<int>,3>calc(vector<int>bounds,vector<int>guys,int state){
  for(int i=0;i<lim;i++)tree[i].clear();
  for(int i=0;i<20;i++)for(int j=0;j<n;j++)jump[i][j]=-1;
  tour.clear();
  tin=tout=vector<int>(n);
  DSU dsu;
  for(int i=state?n-1:0;state?0<=i:i<n;i+=state?-1:1){
    if(state)sort(v[i].begin(),v[i].end());
    else sort(v[i].begin(),v[i].end(),greater<int>());
    for(int j:v[i]){
      int x=dsu.find(i),y=dsu.find(j);
      if((state^(j<i))&&dsu.unite(i,j)){
        tree[x].pb(y);
        jump[0][y]=x;
      }
    }
  }
  // cerr<<"ok\n";
  for(int i=1;i<20;i++){
    for(int j=0;j<n;j++){
      jump[i][j]=jump[i][j]==-1?-1:jump[i-1][jump[i-1][j]];
    }
  }
  // cerr<<"okk\n";
  dfs(state?0:n-1);
  // cerr<<"na bro\n";
  vector<int>l,r;
  for(int i=0;i<q;i++){
    int bd=bounds[i],guy=guys[i];
    for(int j=19;0<=j;j--){
      if(jump[j][guy]!=-1&&(state?bd<=jump[j][guy]:jump[j][guy]<=bd)){
        guy=jump[j][guy];
      }
    }
    l.pb(tin[guy]);
    r.pb(tout[guy]);
  }
  // cerr<<"we gud\n";
  return {tour,l,r};
}

vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
  n=N;
  m=X.size();
  q=S.size();
  for(int i=0;i<m;i++){
    v[X[i]].pb(Y[i]);
    v[Y[i]].pb(X[i]);
  }
  auto[wt,wl,wr]=calc(R,E,0);
  auto[ht,hl,hr]=calc(L,S,1);
  int tr[n];
  for(int i=0;i<n;i++){
    tr[ht[i]]=i;
    // cerr<<ht[i]<<' '<<i<<'\n';
  }
  vector<int>beg[n];
  for(int i=0;i<q;i++){
    beg[wr[i]].pb(i);
  }
  vector<int>ans(q);
  ST st(n);
  // cerr<<"begin\n";
  for(int i=0;i<n;i++){
    // cerr<<"here\n";
    // cerr<<i<<' '<<wt[i]<<' '<<tr[wt[i]]<<'\n';
    st.update(tr[wt[i]],i);
    // cerr<<"whaa\n";
    for(int id:beg[i]){
      int mx=st.query(hl[id],hr[id]);
      ans[id]=mx>=wl[id];
    }
  }
  return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51