Submission #1111642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111642		SalihSahin	Werewolf (IOI18_werewolf)	C++14	0 / 100	755 ms	135248 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;
}

struct SEGT{
  vector<vector<int> > tree;

  void init(int n){
    tree.resize(4*n);
  }

  void update(int ind, int l, int r, int pos1, int pos2){
    if(l == r){
      tree[ind].pb(pos2);
    }
    else{
      int m = (l + r)/2;

      if(pos1 <= m) update(ind*2, l, m, pos1, pos2);
      else update(ind*2+1, m+1, r, pos1, pos2);
      tree[ind].pb(pos2);
    }
  }

  int query(int ind, int l, int r, int ql1, int qr1, int ql2, int qr2){
    if(l > r || l > qr1 || r < ql1) return 0;
    if(l >= ql1 && r <= qr1){
      auto k = lower_bound(tree[ind].begin(), tree[ind].end(), ql2) - tree[ind].begin();
      if(k < tree[ind].size() && tree[ind][k] >= ql2 && tree[ind][k] <= qr2) return 1;
      else return 0;
    }
    else{
      int m = (l + r)/2;

      return query(ind*2, l, m, ql1, qr1, ql2, qr2) + query(ind*2+1, m+1, r, ql1, qr1, ql2, qr2);
    }
  }
};

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);

  SEGT seg;
  seg.init(N);
  for(int i = 0; i < N; i++){
    seg.update(1, 1, N, in2[i], in1[i]);
  }

  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];
    }

    // update {in2, in1}
    // query {{in2[start], out2[start]}, {in1[finish], out1[finish]}}
    int ortak = seg.query(1, 1, N, in2[start], out2[start], in1[finish], out1[finish]);
    /*
    for(int j = L[i]; j <= R[i]; j++){
      bool anc2 = (in2[start] <= in2[j] && out2[start] >= in2[j]);
      bool anc1 = (in1[finish] <= in1[j] && out1[finish] >= in1[j]);
      if(anc1 && anc2){
        ortak = true;
      }
    }
    */
    if(ortak > 0) ans[i] = 1;
  }
  return ans;
}

Compilation message (stderr)

werewolf.cpp: In member function 'int SEGT::query(int, int, int, int, int, int, int)':
werewolf.cpp:92:12: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |       if(k < tree[ind].size() && tree[ind][k] >= ql2 && tree[ind][k] <= qr2) return 1;
      |          ~~^~~~~~~~~~~~~~~~~~

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