Submission #582509

#	Time	Username	Problem	Language	Result	Execution time	Memory
582509		SSRS	Werewolf (IOI18_werewolf)	C++14	34 / 100	631 ms	68220 KiB

werewolf

#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[j]]);
      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[j]]);
      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 (stderr)

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
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51