oj.uz

Submission #1111647

# Submission time Handle Problem Language Result Execution time Memory
1111647 2024-11-12T12:53:19 Z SalihSahin Werewolf (IOI18_werewolf) C++14
100 / 100
 1212 ms 153876 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){
      if(tree[ind].size() > 0){
        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 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]);
  }
  for(int i = 0; i < N*4; i++){
    sort(seg.tree[i].begin(), seg.tree[i].end());
  }

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

werewolf.cpp: In member function 'int SEGT::query(int, int, int, int, int, int, int)':
werewolf.cpp:93:14: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         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 368 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 504 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 368 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 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 9 ms 2384 KB Output is correct
11 Correct 8 ms 2384 KB Output is correct
12 Correct 7 ms 2384 KB Output is correct
13 Correct 8 ms 2384 KB Output is correct
14 Correct 7 ms 2384 KB Output is correct
15 Correct 9 ms 2384 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 801 ms 135428 KB Output is correct
2 Correct 920 ms 146680 KB Output is correct
3 Correct 879 ms 136316 KB Output is correct
4 Correct 817 ms 139808 KB Output is correct
5 Correct 799 ms 139524 KB Output is correct
6 Correct 837 ms 143424 KB Output is correct
7 Correct 830 ms 141876 KB Output is correct
8 Correct 849 ms 146804 KB Output is correct
9 Correct 683 ms 144752 KB Output is correct
10 Correct 677 ms 142356 KB Output is correct
11 Correct 713 ms 141800 KB Output is correct
12 Correct 620 ms 142908 KB Output is correct
13 Correct 836 ms 148336 KB Output is correct
14 Correct 909 ms 148340 KB Output is correct
15 Correct 833 ms 139980 KB Output is correct
16 Correct 838 ms 148276 KB Output is correct
17 Correct 892 ms 143540 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 368 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 504 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 9 ms 2384 KB Output is correct
11 Correct 8 ms 2384 KB Output is correct
12 Correct 7 ms 2384 KB Output is correct
13 Correct 8 ms 2384 KB Output is correct
14 Correct 7 ms 2384 KB Output is correct
15 Correct 9 ms 2384 KB Output is correct
16 Correct 801 ms 135428 KB Output is correct
17 Correct 920 ms 146680 KB Output is correct
18 Correct 879 ms 136316 KB Output is correct
19 Correct 817 ms 139808 KB Output is correct
20 Correct 799 ms 139524 KB Output is correct
21 Correct 837 ms 143424 KB Output is correct
22 Correct 830 ms 141876 KB Output is correct
23 Correct 849 ms 146804 KB Output is correct
24 Correct 683 ms 144752 KB Output is correct
25 Correct 677 ms 142356 KB Output is correct
26 Correct 713 ms 141800 KB Output is correct
27 Correct 620 ms 142908 KB Output is correct
28 Correct 836 ms 148336 KB Output is correct
29 Correct 909 ms 148340 KB Output is correct
30 Correct 833 ms 139980 KB Output is correct
31 Correct 838 ms 148276 KB Output is correct
32 Correct 892 ms 143540 KB Output is correct
33 Correct 1004 ms 143032 KB Output is correct
34 Correct 247 ms 32076 KB Output is correct
35 Correct 1212 ms 147384 KB Output is correct
36 Correct 1073 ms 144376 KB Output is correct
37 Correct 1211 ms 146692 KB Output is correct
38 Correct 1158 ms 145072 KB Output is correct
39 Correct 836 ms 153520 KB Output is correct
40 Correct 899 ms 152860 KB Output is correct
41 Correct 1014 ms 146164 KB Output is correct
42 Correct 776 ms 144268 KB Output is correct
43 Correct 1186 ms 151280 KB Output is correct
44 Correct 1190 ms 146856 KB Output is correct
45 Correct 923 ms 153876 KB Output is correct
46 Correct 1045 ms 153652 KB Output is correct
47 Correct 970 ms 148532 KB Output is correct
48 Correct 840 ms 148400 KB Output is correct
49 Correct 853 ms 148572 KB Output is correct
50 Correct 860 ms 148548 KB Output is correct
51 Correct 849 ms 153528 KB Output is correct
52 Correct 925 ms 153616 KB Output is correct