Submission #1208608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208608		loiiii12358	Werewolf (IOI18_werewolf)	C++20	49 / 100	4104 ms	413032 KiB

werewolf

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

struct SegTree2D{
  int n;
  vector<bool> cnt={false};
  vector<vector<int>> child={{}};
  vector<pair<pair<int,int>,pair<int,int>>> range={make_pair(make_pair(1,1),make_pair(1,1))};
  void init(int N){
    n=N;
    range[0].second=make_pair(N,N);
  }
  void add(int id, int &x,int &y){
    int lx=range[id].first.first,ly=range[id].first.second,rx=range[id].second.first,ry=range[id].second.second;
    if(x<lx||x>rx||y<ly||y>ry){
      return;
    }else if(lx==rx&&ly==ry){
      cnt[id]=true;
      return;
    }
    if(child[id].size()==0){
      int tmp=child.size(),mx=lx+(rx-lx)/2,my=ly+(ry-ly)/2;
      for(int i=0;i<4;i++){
        child[id].push_back(tmp+i);
        child.push_back({});
        cnt.push_back(false);
        range.push_back(make_pair(make_pair(1,1),make_pair(0,0)));
      }
      range[child[id][0]]=make_pair(make_pair(lx,ly),make_pair(mx,my));
      range[child[id][1]]=make_pair(make_pair(mx+1,ly),make_pair(rx,my));
      range[child[id][2]]=make_pair(make_pair(lx,my+1),make_pair(mx,ry));
      range[child[id][3]]=make_pair(make_pair(mx+1,my+1),make_pair(rx,ry));
    }
    for(int i=0;i<4;i++){
      add(child[id][i],x,y);
      cnt[id]=cnt[id]||cnt[child[id][i]];
    }
  }
  bool query(int id,int &Lx,int &Ly,int &Rx,int &Ry){
    int lx=range[id].first.first,ly=range[id].first.second,rx=range[id].second.first,ry=range[id].second.second;
    // cout << id << ' ' << lx << ' ' << ly << ' ' << rx << ' ' << ry << ' ' << cnt[id] << '\n';
    if(Rx<lx||Lx>rx||Ry<ly||Ly>ry){
      return false;
    }else if(lx>=Lx&&rx<=Rx&&ly>=Ly&&ry<=Ry){
      return cnt[id];
    }else if(!cnt[id]){
      return cnt[id];
    }
    bool ans=false;
    for(int i=0;i<4;i++){
      ans=ans||query(child[id][i],Lx,Ly,Rx,Ry);
    }
    return ans;
  }
};

int n;
vector<int> node_wolf,dsu,order_wolf,node_human,order_human;
vector<vector<int>> par_wolf,par_human;
vector<pair<int,int>> edge,child_wolf,bound_wolf,child_human,bound_human;

int find_root(int &u){
  if(u==dsu[u]){
    return u;
  }
  return dsu[u]=find_root(dsu[u]);
}

void dfs_wolf(int u){
  for(int i=1;i<18;i++){
    par_wolf[u][i]=par_wolf[par_wolf[u][i-1]][i-1];
  }
  if(u<n){
    order_wolf.push_back(u);
    bound_wolf[u]={order_wolf.size(),order_wolf.size()};
    return;
  }
  dfs_wolf(child_wolf[u].first);
  dfs_wolf(child_wolf[u].second);
  bound_wolf[u]={bound_wolf[child_wolf[u].first].first,bound_wolf[child_wolf[u].second].second};
}

void dfs_human(int u){
  for(int i=1;i<18;i++){
    par_human[u][i]=par_human[par_human[u][i-1]][i-1];
  }
  if(u<n){
    order_human.push_back(u);
    bound_human[u]={order_human.size(),order_human.size()};
    return;
  }
  dfs_human(child_human[u].first);
  dfs_human(child_human[u].second);
  bound_human[u]={bound_human[child_human[u].first].first,bound_human[child_human[u].second].second};
}

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) {
  n=N;
  int Q = S.size();
  vector<int> A(Q);
  edge.resize(X.size());
  for(int i=0;i<X.size();i++){
    edge[i]={max(X[i],Y[i]),min(X[i],Y[i])};
  }
  sort(edge.begin(),edge.end());
  node_wolf.resize(N);par_wolf.resize(N);dsu.resize(N);child_wolf.resize(N);
  for(int i=0;i<N;i++){
    node_wolf[i]=i;
    par_wolf[i].resize(18,i);
    dsu[i]=i;
  }
  for(int i=0;i<edge.size();i++){
    if(find_root(edge[i].first)!=find_root(edge[i].second)){
      par_wolf[find_root(edge[i].first)][0]=node_wolf.size();
      par_wolf[find_root(edge[i].second)][0]=node_wolf.size();
      child_wolf.push_back({find_root(edge[i].first),find_root(edge[i].second)});
      dsu[find_root(edge[i].first)]=dsu[find_root(edge[i].second)]=node_wolf.size();
      node_wolf.push_back(edge[i].first);
      par_wolf.push_back(vector<int>(18,par_wolf.size()));
      dsu.push_back(dsu.size());
    }
  }
  bound_wolf.resize(dsu.size());
  dfs_wolf(bound_wolf.size()-1);
  for(int i=0;i<X.size();i++){
    edge[i]={min(X[i],Y[i]),max(X[i],Y[i])};
  }
  sort(edge.begin(),edge.end());
  node_human.resize(N);par_human.resize(N);dsu.clear();dsu.resize(N);child_human.resize(N);
  for(int i=0;i<N;i++){
    node_human[i]=i;
    par_human[i].resize(18,i);
    dsu[i]=i;
  }
  for(int i=edge.size()-1;i>=0;i--){
    if(find_root(edge[i].first)!=find_root(edge[i].second)){
      par_human[find_root(edge[i].first)][0]=node_human.size();
      par_human[find_root(edge[i].second)][0]=node_human.size();
      child_human.push_back({find_root(edge[i].first),find_root(edge[i].second)});
      dsu[find_root(edge[i].first)]=dsu[find_root(edge[i].second)]=node_human.size();
      node_human.push_back(edge[i].first);
      par_human.push_back(vector<int>(18,par_human.size()));
      dsu.push_back(dsu.size());
    }
  }
  bound_human.resize(dsu.size());
  dfs_human(bound_human.size()-1);
  SegTree2D ds;ds.init(N);
  vector<pair<int,int>> coor;
  coor.resize(order_human.size());
  for(int i=0;i<order_human.size();i++){
    coor[order_human[i]].first=i+1;
    coor[order_wolf[i]].second=i+1;
  }
  for(int i=0;i<order_human.size();i++){
    ds.add(0,coor[i].first,coor[i].second);
  }
  for(int i=0;i<Q;i++){
    for(int j=17;j>=0;j--){
      if(node_human[par_human[S[i]][j]]>=L[i]){
        S[i]=par_human[S[i]][j];
      }
      if(node_wolf[par_wolf[E[i]][j]]<=R[i]){
        E[i]=par_wolf[E[i]][j];
      }
    }
    if(ds.query(0,bound_human[S[i]].first,bound_wolf[E[i]].first,bound_human[S[i]].second,bound_wolf[E[i]].second)){
      A[i]=1;
    }else{
      A[i]=0;
    }
  }
  return A;
}
//Nlog(N)
//Qlog(N)^2

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