Submission #1219960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219960		Malix	Werewolf (IOI18_werewolf)	C++20	100 / 100	1593 ms	395800 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) x.begin(),x.end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

vii a,b,c,d,e;
int n,m,pos;
vi p,arr,brr;
vector<set<int>> st;

int parent(int x){
  if(p[x]==x)return x;
  else return p[x]=parent(p[x]);
}

void merge(int x,int y,int z){
  p[y]=z;
  p[x]=z;
}

void dfs(int x,vii &ed,vi &ar,vii &par,vi &P,vi &C){
  if(x<n){
    ar.PB(x);
    C[x]=ar.size()-1;
  }
  for(auto u:ed[x])if(par[x][0]!=u){
    dfs(u,ed,ar,par,P,C);
    P[x]+=P[u];
    C[x]=min(C[x],C[u]);
  }
}

void build(int x,int l,int r){
  if(l==r){
    st[x].insert(brr[l]);
    return;
  }
  int m=(l+r)/2;
  build(2*x,l,m);
  build(2*x+1,m+1,r);
  for(auto u:st[2*x])st[x].insert(u);
  for(auto u:st[2*x+1])st[x].insert(u);
}

bool query(int x,int l,int r,int u,int v,int t1,int t2){
  if(u>v)return 0;
  if(l==u&&r==v){
    auto it=st[x].lower_bound(t1);
    if(it==st[x].end())return 0;
    return (*it<=t2);
  }
  int m=(l+r)/2;
  return (query(2*x,l,m,u,min(m,v),t1,t2)||query(2*x+1,m+1,r,max(u,m+1),v,t1,t2));
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  m=S.size();
  n=N;
  a.resize(n);
  vi ans(m,0);
  REP(i,0,X.size()){
    a[X[i]].PB(Y[i]);
    a[Y[i]].PB(X[i]);
  }
  vi P(2*n+1,0),Q(2*n+1,0),A(2*n+1,inf),B(2*n+1,-inf),C(2*n+1,inf),D(2*n+1,inf);
  REP(i,0,n)A[i]=i;REP(i,0,n)B[i]=i;
  REP(i,0,n)P[i]=1;REP(i,0,n)Q[i]=1;
  p.resize(2*n+1);
  REP(i,0,2*n+1)p[i]=i;
  int k=log2(2*n+1)+1;
  d.resize(2*n+1,vi(k,-1));e.resize(2*n+1,vi(k,-1));
  b.resize(2*n+1);c.resize(2*n+1);
  pos=n;
  for(int i=n-1;i>=0;i--){
    set<int> st;
    for(auto u:a[i])if(u>i)st.insert(parent(u));
    for(auto u:st){
      merge(u,i,pos);
      d[u][0]=pos;
      b[pos].PB(u);
      A[pos]=min(A[pos],A[u]);
    }
    d[i][0]=pos;
    b[pos].PB(i);
    A[pos]=min(A[pos],A[i]);
    pos++;
  }
  dfs(pos-1,b,arr,d,P,C);
  pos=n;
  p.clear();p.resize(2*n+1);
  REP(i,0,2*n+1)p[i]=i;
  REP(i,0,n){
    set<int> st;
    for(auto u:a[i])if(u<i)st.insert(parent(u));
    for(auto u:st){
      merge(u,i,pos);
      e[u][0]=pos;
      c[pos].PB(u);
      B[pos]=max(B[pos],B[u]);
    }
    e[i][0]=pos;
    c[pos].PB(i);
    B[pos]=max(B[pos],B[i]);
    pos++;
  }
  dfs(pos-1,c,brr,e,Q,D);
  REP(j,1,k)REP(i,0,2*n+1)if(d[i][j-1]!=-1)d[i][j]=d[d[i][j-1]][j-1];
  REP(j,1,k)REP(i,0,2*n+1)if(e[i][j-1]!=-1)e[i][j]=e[e[i][j-1]][j-1];
  st.resize(4*n+1);
  vi tmp(n);
  REP(i,0,n)tmp[arr[i]]=i;
  REP(i,0,n)brr[i]=tmp[brr[i]];
  build(1,0,n-1);
  REP(i,0,m){
    int x=L[i],y=R[i],p1=S[i],p2=E[i];
    for(int j=k-1;j>=0;j--)if(d[p1][j]!=-1&&A[d[p1][j]]>=x)p1=d[p1][j];
    for(int j=k-1;j>=0;j--)if(e[p2][j]!=-1&&B[e[p2][j]]<=y)p2=e[p2][j];
    if(query(1,0,n-1,D[p2],D[p2]+Q[p2]-1,C[p1],C[p1]+P[p1]-1))ans[i]=1;
  }
  return ans;
}

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