oj.uz

Submission #1111645

# Submission time Handle Problem Language Result Execution time Memory
1111645 2024-11-12T12:48:55 Z SalihSahin Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 89672 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 = 0; j <= N-1; 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 336 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 336 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 26 ms 1616 KB Output is correct
11 Correct 33 ms 1784 KB Output is correct
12 Correct 38 ms 1616 KB Output is correct
13 Correct 22 ms 1928 KB Output is correct
14 Correct 27 ms 1872 KB Output is correct
15 Correct 20 ms 1864 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4064 ms 89672 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 336 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 26 ms 1616 KB Output is correct
11 Correct 33 ms 1784 KB Output is correct
12 Correct 38 ms 1616 KB Output is correct
13 Correct 22 ms 1928 KB Output is correct
14 Correct 27 ms 1872 KB Output is correct
15 Correct 20 ms 1864 KB Output is correct
16 Execution timed out 4064 ms 89672 KB Time limit exceeded
17 Halted 0 ms 0 KB -