oj.uz

Submission #1042985

# Submission time Handle Problem Language Result Execution time Memory
1042985 2024-08-03T16:58:53 Z thatsgonzalez Werewolf (IOI18_werewolf) C++14
7 / 100
 4000 ms 29820 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5+100;

vector<vector<int>> g;
bitset <nmax> vis1, vis2;
bool res = false;


void dfs(int node, int endpoint, int l, int r, bool estado, int pivot){

  if(pivot == node){
    estado = true;
  }
  
  if(!estado and node<l) {
    return;
  }
  if(estado and node>r) return;
  if(node == endpoint and estado){
    res = true; return;
  }

  /*if(!estado)*/ vis1[node] = 1;
  //else vis2[node] = 1;

  for(auto &x: g[node]){
    if(vis1[x] /*and !estado*/) continue;
    //if(vis2[x] and estado) continue;

    /*if(x>=l and x<=r and !estado){
      dfs(x,endpoint,l,r,estado);
      dfs(x,endpoint,l,r,!estado);
    }
    else{*/
      dfs(x,endpoint,l,r,estado,pivot);
    //}

  }

}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
  int Q = S.size();
  int M = X.size();
  std::vector<int> ans(Q,0);

  g.resize(N);
  
  for(int i = 0; i<M; i++){

    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);

  }

  for(int q = 0; q<Q; q++){

    res = false;

    for(int i = L[q]; i<=R[q]; i++){
        dfs(S[q],E[q],L[q],R[q],0,i);
        vis1.reset();
    }

    ans[q] = res;
    //vis2.reset();

  }
  g.clear();

  return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 2 ms 436 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Execution timed out 4058 ms 860 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 2 ms 436 KB Output is correct
9 Correct 2 ms 436 KB Output is correct
10 Execution timed out 4058 ms 860 KB Time limit exceeded
11 Halted 0 ms 0 KB -