제출 #1183744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183744		dzuizz	늑대인간 (IOI18_werewolf)	C++20	0 / 100	196 ms	55884 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
constexpr int MAXN=200005,LOG=18;

vector<int> adj[MAXN],nx[MAXN];
bool vis[MAXN];
int pre[MAXN],pos[MAXN],dep[MAXN];
int pa[2][MAXN][LOG];
int ldr[2][MAXN];
int _ptr;

int f(int x,int k){ return x==ldr[k][x]?x:ldr[k][x]=f(ldr[k][x],k); }

void merge(int a,int b,int k){
  a=f(a,k),b=f(b,k);
  if(a==b) return;
  pa[k][b][0]=a,ldr[k][b]=a;
}

/*
void dfs(int i,int k){
  if(k) sort(adj[i].begin(),adj[i].end(),greater<int>());
  else sort(adj[i].begin(),adj[i].end());
  v[k][i][0]=i,vis[i]=1;
  for(auto&x:adj[i]){
    if(vis[x]) continue;
    pa[k][x][0]=i,dep[k][x]=dep[k][i]+1;
    dfs(x,k);
  }
}
*/

void dfs(int i){
  pre[i]=_ptr;
  for(auto&x:nx[i]){
    dep[x]=dep[i]+1;
    dfs(x);
  }
  pos[i]=++_ptr;
}

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 M=X.size(),Q=S.size();

  for(int i=0;i<M;++i){
    adj[X[i]].emplace_back(Y[i]);
    adj[Y[i]].emplace_back(X[i]);
  }

  for(int i=0;i<N;++i) pa[0][i][0]=i,pa[1][i][0]=i,ldr[0][i]=i,ldr[1][i]=1;
  for(int i=N-1;i>=0;--i) for(auto&x:adj[i]) if(x>i) merge(i,x,0);
  for(int i=0;i<N;++i) for(auto&x:adj[i]) if(x<i) merge(i,x,1);

  /*
  dfs(0,0);  // min
  memset(vis,0,sizeof vis);
  pa[1][N-1][0]=N-1;
  dfs(N-1,1);  // max
  */

  for(int j=0;j<LOG-1;++j) for(int i=0;i<N;++i)
    pa[0][i][j+1]=pa[0][pa[0][i][j]][j],
    pa[1][i][j+1]=pa[1][pa[1][i][j]][j];

  for(int i=0;i<N;++i) if(pa[1][i][0]!=i)
    nx[pa[1][i][0]].emplace_back(i);
  dfs(pa[1][0][LOG-1]);

  /*
  for(int i=0;i<N;++i)
    cout<<dep[1][i]<<" ";
  cout<<'\n';
  */

  vector<int> A(Q,0);
  for(int i=0;i<Q;++i){
    int a=S[i];
    for(int j=LOG-1;j>=0;--j)if(pa[0][a][j]>=L[i])
      a=pa[0][a][j];
    int t=a,b=E[i];
    //cout<<a<<" "<<b<<'\n';
    for(int j=LOG-1;j>=0;--j) if(dep[pa[1][a][j]]>=dep[b])
      a=pa[1][a][j];
    if(a>R[i]) continue;
    if(a==b){
      A[i]=1;
    }else{
      if(dep[a]<dep[b]) swap(a,b);
      for(int j=LOG-1;j>=0;--j) if(pa[1][a][j]!=pa[1][b][j])
        a=pa[1][a][j],b=pa[1][b][j];
      int c=pa[1][a][0];
      if(c<=R[i]) A[i]=1;
    }
    /*
    if(dep[1][a]<dep[1][b]) swap(a,b);
    int maxi=0;
    cout<<a<<" "<<b<<" "<<'\n';
    for(int j=LOG-1;j>=0;--j)if(dep[1][pa[1][a][j]]>=dep[1][b])
      maxi=max(maxi,v[1][a][j]),a=pa[1][a][j];
    cout<<a<<" "<<b<<" "<<maxi<<'\n';
    if(maxi<=R[i]) A[i]=1;
    else A[i]=0;
    */
  }
  return A;
}

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