제출 #582510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582510		SSRS	늑대인간 (IOI18_werewolf)	C++14	34 / 100	666 ms	59880 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;
}

컴파일 시 표준 에러 (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