oj.uz

Submission #582507

# Submission time Handle Problem Language Result Execution time Memory
582507 2022-06-24T01:51:34 Z SSRS Werewolf (IOI18_werewolf) C++14
0 / 100
 610 ms 68132 KB 
#include <bits/stdc++.h>
using namespace std;
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 M = X.size();
  int Q = S.size();
  vector<vector<int>> G(N);
  for (int i = 0; i < M; i++){
    G[X[i]].push_back(Y[i]);
    G[Y[i]].push_back(X[i]);
  }
  int r;
  for (int i = 0; i < N; i++){
    if (G[i].size() == 1){
      r = i;
    }
  }
  vector<int> p(N, -1);
  p[r] = 0;
  for (int i = 1; i < N; i++){
    for (int v : G[r]){
      if (p[v] == -1){
        p[v] = i;
        r = v;
        break;
      }
    }
  }
  vector<vector<int>> query1(N);
  for (int i = 0; i < Q; i++){
    query1[L[i]].push_back(i);
  }
  vector<int> L1(Q, 0), R1(Q, N);
  set<int> st1;
  for (int i = 0; i < N; i++){
    for (int j : query1[i]){
      auto itr = st1.lower_bound(p[S[i]]);
      if (itr != st1.end()){
        R1[j] = *itr;
      }
      if (itr != st1.begin()){
        L1[j] = *prev(itr) + 1;
      }
    }
    st1.insert(p[i]);
  }
  vector<vector<int>> query2(N);
  for (int i = 0; i < Q; i++){
    query2[R[i]].push_back(i);
  }
  vector<int> L2(Q, 0), R2(Q, N);
  set<int> st2;
  for (int i = N - 1; i >= 0; i--){
    for (int j : query2[i]){
      auto itr = st2.lower_bound(p[E[i]]);
      if (itr != st2.end()){
        R2[j] = *itr;
      }
      if (itr != st2.begin()){
        L2[j] = *prev(itr) + 1;
      }
    }
    st2.insert(p[i]);
  }
  vector<int> ans(Q);
  for (int i = 0; i < Q; i++){
    if (max(L1[i], L2[i]) < min(R1[i], R2[i])){
      ans[i] = 1;
    } else {
      ans[i] = 0;
    }
  }
  return ans;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:18:6: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   18 |   p[r] = 0;
      |      ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 610 ms 68132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -