Submission #1111635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111635		SalihSahin	Werewolf (IOI18_werewolf)	C++14	15 / 100	4033 ms	89672 KiB

werewolf

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

const int K = 18;

vector<int> par;
vector<vector<int> > adj1, adj2, adj;

int fnd(int a){
  if(a == par[a]) return a;
  return par[a] = fnd(par[a]);
}

bool merge(int a, int b, int g){
  a = fnd(a), b = fnd(b);
  if(a == b) return 0;

  if(g == 0){
    adj1[a].pb(b);
    adj1[b].pb(a);
    par[min(a, b)] = max(a, b);
  }
  else{
    adj2[a].pb(b);
    adj2[b].pb(a);
    par[max(a, b)] = min(a, b);
  }

  return 1;
}

vector<int> in1, out1, in2, out2, p1, p2;
vector<vector<int> > jump1, jump2;
int timer;

void dfs1(int node, int par){
  in1[node] = ++timer;
  p1[node] = par;
  jump1[node][0] = par;
  for(int i = 1; i < K; i++){
    jump1[node][i] = jump1[jump1[node][i-1]][i-1];
  }

  for(auto itr: adj1[node]){
    if(itr == par) continue;
    dfs1(itr, node);
  }
  out1[node] = timer;
}

void dfs2(int node, int par){
  in2[node] = ++timer;
  p2[node] = par;
  jump2[node][0] = par;
  for(int i = 1; i < K; i++){
    jump2[node][i] = jump2[jump2[node][i-1]][i-1];
  }
  
  for(auto itr: adj2[node]){
    if(itr == par) continue;
    dfs2(itr, node);
  }
  out2[node] = timer;
}

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();
  adj1.resize(N);
  adj2.resize(N);
  adj.resize(N);
  par.resize(N);
  in1.resize(N);
  in2.resize(N);
  out1.resize(N);
  out2.resize(N);
  p1.resize(N);
  p2.resize(N);
  jump1.resize(N);
  jump2.resize(N);
  for(int i = 0; i < N; i++){
    jump1[i].resize(K);
    jump2[i].resize(K);
  }


  for(int i = 0; i < m; i++){
    adj[X[i]].pb(Y[i]);
    adj[Y[i]].pb(X[i]);
  }
  for(int i = 0; i < N; i++){
    par[i] = i;
  }

  for(int i = 0; i < N; i++){
    for(auto itr: adj[i]){
      if(itr > i) continue;
      merge(i, itr, 0);
    }
  } // adj1'i oluşturuyoruz -> werewolf path

  for(int i = 0; i < N; i++){
    par[i] = i;
  }

  for(int i = N-1; i >= 0; i--){
    for(auto itr: adj[i]){
      if(itr < i) continue;
      merge(i, itr, 1);
    }
  } // adj2'yi oluşturuyoruz -> human path
  timer = 0;
  dfs1(N-1, N-1);
  timer = 0;
  dfs2(0, 0);
  

  vector<int> ans(q);
  for (int i = 0; i < q; ++i) {
    int start = S[i], finish = E[i];
    for(int j = K-1; j >= 0; j--){
      if(jump2[start][j] < L[i]) continue;
      start = jump2[start][j];
    }
    for(int j = K-1; j >= 0; j--){
      if(jump1[finish][j] > R[i]) continue;
      finish = jump1[finish][j];
    }

    bool ortak = 0;
    for(int j = L[i]; j <= R[i]; j++){
      bool anc2 = (in2[start] <= in2[j] && out2[start] >= out2[j]);
      bool anc1 = (in1[finish] <= in1[j] && out1[finish] >= out1[j]);
      if(anc1 && anc2){
        ortak = true;
      }
    }

    if(ortak) ans[i] = 1;
  }
  return ans;
}

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