oj.uz

Submission #1111635

# Submission time Handle Problem Language Result Execution time Memory
1111635 2024-11-12T12:24:06 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;
}

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.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 17 ms 1616 KB Output is correct
11 Correct 22 ms 1792 KB Output is correct
12 Correct 27 ms 1616 KB Output is correct
13 Correct 13 ms 1872 KB Output is correct
14 Correct 16 ms 1872 KB Output is correct
15 Correct 16 ms 1868 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4033 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 17 ms 1616 KB Output is correct
11 Correct 22 ms 1792 KB Output is correct
12 Correct 27 ms 1616 KB Output is correct
13 Correct 13 ms 1872 KB Output is correct
14 Correct 16 ms 1872 KB Output is correct
15 Correct 16 ms 1868 KB Output is correct
16 Execution timed out 4033 ms 89672 KB Time limit exceeded
17 Halted 0 ms 0 KB -