oj.uz

Submission #1111643

# Submission time Handle Problem Language Result Execution time Memory
1111643 2024-11-12T12:48:08 Z SalihSahin Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 89700 KB 
#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]);
    int ortak = 0;
    
    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 = 1;
      }
    }
  
    if(ortak > 0) ans[i] = 1;
  }
  return ans;
}

Compilation message

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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 17 ms 1944 KB Output is correct
11 Correct 22 ms 1784 KB Output is correct
12 Correct 24 ms 1876 KB Output is correct
13 Correct 14 ms 1884 KB Output is correct
14 Correct 16 ms 1872 KB Output is correct
15 Correct 18 ms 1872 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4077 ms 89700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 17 ms 1944 KB Output is correct
11 Correct 22 ms 1784 KB Output is correct
12 Correct 24 ms 1876 KB Output is correct
13 Correct 14 ms 1884 KB Output is correct
14 Correct 16 ms 1872 KB Output is correct
15 Correct 18 ms 1872 KB Output is correct
16 Execution timed out 4077 ms 89700 KB Time limit exceeded
17 Halted 0 ms 0 KB -