Submission #1111713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111713		epicci23	Werewolf (IOI18_werewolf)	C++17	0 / 100	300 ms	117064 KiB

werewolf

#include "bits/stdc++.h"
#include "werewolf.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1000000007;
const int N = 400005;
const int LOG = 20;

struct DSU{
  vector<int> par,siz,mini;
  DSU(int _n){
   par.resize(_n+5);
   iota(all(par),0);
   siz.assign(_n+5,1);
   mini.resize(_n+5);
   iota(all(mini),0);
  } 
  int find(int a){
    if(par[a]==a) return a;
    return par[a]=find(par[a]);
  }
  void merge(int a,int b){
    a=find(a),b=find(b);
    if(a==b) return;
    if(siz[a]>siz[b]) swap(a,b);
    par[a]=b;
    siz[b]+=siz[a];
  }
};

vector<int> v[N],human[N],wolf[N];
vector<int> hin(N,INF),hout(N,-INF),win(N,INF),wout(N,-INF);
int wift[N][LOG],hift[N][LOG],Tman[N],Twolf[N],hp,wp,ptr;

void hfs(int c){
  if(sz(human[c])){
    hout[c]=hin[c]=++ptr;
    return;
  }
  for(int i=1;i<LOG;i++) hift[c][i]=hift[hift[c][i-1]][i-1];
  for(int x:human[c]){
    hift[x][0]=c;
    hfs(x);
    hin[c]=min(hin[c],hin[x]);
    hout[c]=max(hout[c],hout[x]);
  }
}

void wfs(int c){
  if(sz(wolf[c])){
    wout[c]=win[c]=++ptr;
    return;
  }
  for(int i=1;i<LOG;i++) wift[c][i]=wift[wift[c][i-1]][i-1];
  for(int x:wolf[c]){
    wift[x][0]=c;
    wfs(x);
    win[c]=min(win[c],win[x]);
    wout[c]=max(wout[c],wout[x]);
  }
}

struct SegT{
  vector<vector<int>> seg;
  SegT(int _n){
    seg.resize(4*_n+5);
  }
  void add(int rt,int l,int r,int ind,int u){
    if(r<ind || l>ind) return;
    if(l==r){
      seg[rt].push_back(u);
      return;
    }
    int m=(l+r)/2;
    add(rt*2,l,m,ind,u),add(rt*2+1,m+1,r,ind,u);
    seg[rt].push_back(u);
  }
  int query(int rt,int l,int r,int gl,int gr,int bl,int br){
    if(r<gl || l>gr) return 0;
    if(l>=gl && r<=gr){
      int it = lower_bound(all(seg[rt]),bl) - seg[rt].begin();
      if(it<sz(seg[rt]) && seg[rt][it]<=br) return 1;
      return 0;
    }
    int m=(l+r)/2;
    return query(rt*2,l,m,gl,gr,bl,br) + query(rt*2+1,m+1,r,gl,gr,bl,br);
  }
};

vector<int> check_validity(int _N, vector<int> X, vector<int> Y,vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
  int n=_N,m=sz(X),q=sz(L);

  for(int i=0;i<m;i++){
 	 int a=X[i],b=Y[i];
   v[a].push_back(b);
 	 v[b].push_back(a);
  }
  
  hp=n;
  DSU dsu(N),dsu2(N);

  for(int i=n-1;i>=0;i--){
    for(int x:v[i]){
      if(x>i){
        int A = dsu.find(i), B = dsu.find(x);
        if(A==B) continue;
        int parA = dsu.mini[dsu.find(i)], parB = dsu.mini[dsu.find(x)];
        dsu.merge(A,B);
        human[hp].push_back(parA);
        human[hp].push_back(parB);
        Tman[hp]=i;
        dsu.mini[dsu.find(A)]=hp++;
      }
    }
  }
 
  wp=n;
  for(int i=0;i<n;i++){
    for(int x:v[i]){
      if(x<i){
        int A = dsu2.find(i), B = dsu2.find(x);
        if(A==B) continue;
        int parA = dsu2.mini[dsu2.find(i)], parB = dsu2.mini[dsu2.find(x)];
        dsu2.merge(A,B);
        wolf[wp].push_back(parA);
        wolf[wp].push_back(parB);
        Twolf[wp]=i;
        dsu2.mini[dsu2.find(A)]=wp++;
      }
    }
  }
  
  for(int i=0;i<LOG;i++) wift[wp][i]=wp,hift[hp][i]=hp;
  ptr=0;
  hfs(hp);
  ptr=0;
  wfs(wp);
  
  SegT T(N);

  for(int i=0;i<n;i++) T.add(1,1,n,hin[i],win[i]);
  for(int i=0;i<sz(T.seg);i++) sort(all(T.seg[i]));


  vector<int> res(q,0);

  for(int i=0;i<q;i++){
    int st = S[i], fn = E[i];
    for(int j=LOG-1;j>=0;j--){
      if(Tman[hift[st][j]] < L[i]) continue;
      st = hift[st][j];
    }
    for(int j=LOG-1;j>=0;j--){
      if(Twolf[wift[fn][j]] > R[i]) continue;
      fn = wift[fn][j];
    }
    if(T.query(1,1,n,hin[st],hout[st],win[fn],wout[fn])) res[i]=1;
    else res[i]=0;
  }


  return res;
}

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