oj.uz

답안 #582510

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

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 666 ms 59764 KB Output is correct
2 Correct 354 ms 59796 KB Output is correct
3 Correct 401 ms 59880 KB Output is correct
4 Correct 414 ms 59784 KB Output is correct
5 Correct 509 ms 59784 KB Output is correct
6 Correct 515 ms 59724 KB Output is correct
7 Correct 524 ms 57588 KB Output is correct
8 Correct 359 ms 59784 KB Output is correct
9 Correct 383 ms 58852 KB Output is correct
10 Correct 372 ms 58572 KB Output is correct
11 Correct 434 ms 58640 KB Output is correct
12 Correct 537 ms 59396 KB Output is correct
13 Correct 386 ms 59796 KB Output is correct
14 Correct 392 ms 59780 KB Output is correct
15 Correct 391 ms 59780 KB Output is correct
16 Correct 388 ms 59852 KB Output is correct
17 Correct 465 ms 57436 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -