Submission #1068980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068980		Huseyn123	Werewolf (IOI18_werewolf)	C++17	100 / 100	867 ms	138996 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h> 
#define MAX 200001
#define pb push_back
using namespace std; 
vector<int> f(vector<int> &a,vector<int> &b){
    int i,j;
    i=j=0;
    vector<int> res;
    while(i<(int)a.size() && j<(int)b.size()){
        if(a[i]<b[j]){
            res.pb(a[i]);
            i++;
        }
        else{
            res.pb(b[j]);
            j++;
        }
    }
    while(i<(int)a.size()){
        res.pb(a[i]);
        i++;
    }
    while(j<(int)b.size()){
        res.pb(b[j]);
        j++;
    }
    return res;
}
struct segtree{
    int size;
    vector<vector<int>> tree;
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        tree.resize(2*size);
    }
    void build(vector<int> &a,int x,int lx,int rx){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                tree[x]={a[lx]};
            }
            return;
        }
        int m=(lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        tree[x]=f(tree[2*x+1],tree[2*x+2]);
    }
    void build(vector<int> &a){
        build(a,0,0,size);
    }
    bool get_res(int l,int r,int x,int lx,int rx,int l1,int r1){
        if(lx>=r || rx<=l){
            return false;
        }
        if(lx>=l && rx<=r){
            auto it=lower_bound(tree[x].begin(),tree[x].end(),l1);
            if(it==tree[x].end() || *it>r1){
              return false;
            }
            return true;
        }
        int m=(lx+rx)/2;
        bool s1,s2;
        s1=get_res(l,r,2*x+1,lx,m,l1,r1);
        s2=get_res(l,r,2*x+2,m,rx,l1,r1);
        s1|=s2;
        return s1;
    }
    bool get_res(int l,int r,int l1,int r1){
        return get_res(l,r,0,0,size,l1,r1);
    }
};
struct DSU{
  vector<int> e,mx,mn;
  void init(int n){
    e.resize(n,-1);
    mx.resize(n); 
    mn.resize(n); 
    for(int i=0;i<n;i++){
      mn[i]=i; 
      mx[i]=i; 
    }
  }
  int get(int x){
    if(e[x]<0){
      return x;
    }
    return e[x]=get(e[x]);
  }
  int get_mn(int x){
    return mn[get(x)]; 
  }
  int get_mx(int x){
    return mx[get(x)]; 
  }
  bool unite(int x,int y){
    x=get(x); 
    y=get(y); 
    if(x==y) return false; 
    if(e[x]<e[y]){
      swap(x,y);
    }
    e[y]+=e[x];
    mx[y]=max(mx[y],mx[x]);
    mn[y]=min(mn[y],mn[x]);
    e[x]=y;
    return true;
  }
};
int bl1[MAX][20],bl2[MAX][20],in1[MAX],in2[MAX],out1[MAX],out2[MAX];
int tim=-1; 
vector<vector<int>> g,g1,g2;
void dfs1(int v){
  in1[v]=++tim; 
  for(auto x:g1[v]){
    if(in1[x]!=-1){
      continue;
    }
    dfs1(x);
  }
  out1[v]=tim;
}
void dfs2(int v){
  in2[v]=++tim; 
  for(auto x:g2[v]){
    if(in2[x]!=-1){
      continue;
    }
    dfs2(x);
  }
  out2[v]=tim;
}
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 Q = S.size();
  int M = X.size();
  g.clear(); 
  g.resize(N);
  g1.clear(); 
  g1.resize(N);
  g2.clear(); 
  g2.resize(N);
  vector<int> A(Q);
  for (int i = 0; i < Q; ++i) {
    A[i] = 0;
  }
  DSU dsu1,dsu2; 
  dsu1.init(N); 
  dsu2.init(N); 
  for(int i=0;i<M;i++){
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  for(int i=0;i<N;i++){
    bl1[i][0]=bl2[i][0]=in1[i]=in2[i]=-1;
  }
  for(int i=0;i<N;i++){
    for(auto x:g[i]){
      int h=dsu1.get_mx(x);
      if(x<i && dsu1.unite(i,x)){
        g1[i].push_back(h); 
        g1[h].push_back(i);
        bl1[h][0]=i;
      }
    }
  }
  for(int i=N-1;i>=0;i--){
    for(auto x:g[i]){
      int h=dsu2.get_mn(x);
      if(x>i && dsu2.unite(i,x)){ 
        g2[i].push_back(h); 
        g2[h].push_back(i);
        bl2[h][0]=i;
      }
    }
  }
  for(int i=1;i<20;i++){
    for(int j=0;j<N;j++){
      if(bl1[j][i-1]==-1){
         bl1[j][i]=-1;
      }
      else{
        bl1[j][i]=bl1[bl1[j][i-1]][i-1];
      }
      if(bl2[j][i-1]==-1){
         bl2[j][i]=-1;
      }
      else{
        bl2[j][i]=bl2[bl2[j][i-1]][i-1];
      }
    }
  }
  tim=-1;
  for(int i=N-1;i>=0;i--){
    if(in1[i]!=-1){
      continue; 
    }
    dfs1(i); 
  }
  tim=-1;
  for(int i=0;i<N;i++){
    if(in2[i]!=-1){
      continue; 
    }
    dfs2(i); 
  }
  vector<int> a(N); 
  for(int i=0;i<N;i++){
    a[in1[i]]=in2[i];
  }
  segtree st; 
  st.init(N); 
  st.build(a); 
  for(int i=0;i<Q;i++){
    for(int j=19;j>=0;j--){
      if(bl1[E[i]][j]!=-1 && bl1[E[i]][j]<=R[i]){
        E[i]=bl1[E[i]][j];
      }
    }
    for(int j=19;j>=0;j--){
      if(bl2[S[i]][j]!=-1 && bl2[S[i]][j]>=L[i]){
        S[i]=bl2[S[i]][j];
      }
    }
    A[i]=st.get_res(in1[E[i]],out1[E[i]]+1,in2[S[i]],out2[S[i]]);
  }
  return A;
}

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