Submission #1038701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038701		boyliguanhan	Werewolf (IOI18_werewolf)	C++17	100 / 100	492 ms	126036 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define M 200100
typedef vector<int> VI;
struct dsu{
  int par[M];
  int abp(int n){
    return par[n]?par[n]=abp(par[n]):n;
  }
  int merge(int a,int b){
    a++;b++;
    a=abp(a),b=abp(b);
    if(a-b)par[a]=b;
    return a!=b;
  }
} dsuhuman,dsuwolf;
int bjh[M][20],bjw[M][20],in[M],out[M],CC;
vector<pair<int,int>>qry[M];
set<int>st[M];
VI EDGES[M],adjh[M],adjw[M];
vector<int>ans;
void dfsw(int n){
  in[n]=++CC;
  for(auto i:adjw[n])
    dfsw(i);
  out[n]=CC;
}
void merge(int a,int b){
  if(st[a].size()<st[b].size())
    swap(st[a],st[b]);
  for(auto i:st[b])
    st[a].insert(i);
  st[b].clear();
}
void dfsans(int n){
  st[n].insert(in[n]);
  for(auto i:adjh[n])
    dfsans(i),merge(n,i);
  for(auto[i,x]:qry[n])
    ans[i]=st[n].lower_bound(in[x])!=
          st[n].upper_bound(out[x]);
}
VI check_validity(int N,VI X,VI Y,VI S,VI E,VI L,VI R) {
  for(int i=0;i<X.size();i++)
    EDGES[X[i]].push_back(Y[i]),
    EDGES[Y[i]].push_back(X[i]);
  for(int i=N;i--;)
    for(auto k:EDGES[i]) {
      if(k<i)continue;
      int x=dsuhuman.abp(k+1)-1;
      if(x==i) continue;
      bjh[x][0]=i,adjh[i].push_back(x);
      dsuhuman.merge(x,i);
    }
  for(int i=0;i<N;i++)
    for(auto k:EDGES[i]) {
      if(k>i)continue;
      int x=dsuwolf.abp(k+1)-1;
      if(x==i) continue;
      bjw[x][0]=i,adjw[i].push_back(x);
      dsuwolf.merge(x,i);
    }
  bjw[N-1][0]=bjw[N][0]=N;
  for(int j=1;j<20;j++)
    for(int i=0;i<=N;i++)
      bjw[i][j]=bjw[bjw[i][j-1]][j-1],
      bjh[i][j]=bjh[bjh[i][j-1]][j-1];
  dfsw(N-1);
  int Q=S.size();
  ans=S;
  for(int i=0;i<Q;i++){
    int l=L[i],r=R[i],s=S[i],e=E[i];
    for(int i=20;i--;)
      if(bjh[s][i]>=l)
        s=bjh[s][i];
    for(int i=20;i--;)
      if(bjw[e][i]<=r)
        e=bjw[e][i];
    qry[s].push_back({i,e});
  }
  dfsans(0);
  return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'VI check_validity(int, VI, VI, VI, VI, VI, VI)':
werewolf.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int i=0;i<X.size();i++)
      |               ~^~~~~~~~~

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