oj.uz

Submission #582509

# Submission time Handle Problem Language Result Execution time Memory
582509 2022-06-24T01:55:30 Z SSRS Werewolf (IOI18_werewolf) C++14
34 / 100
 631 ms 68220 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

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 59688 KB Output is correct
2 Correct 382 ms 68188 KB Output is correct
3 Correct 426 ms 68172 KB Output is correct
4 Correct 455 ms 68220 KB Output is correct
5 Correct 435 ms 68188 KB Output is correct
6 Correct 522 ms 68220 KB Output is correct
7 Correct 502 ms 65984 KB Output is correct
8 Correct 405 ms 68100 KB Output is correct
9 Correct 341 ms 67152 KB Output is correct
10 Correct 383 ms 66932 KB Output is correct
11 Correct 431 ms 67020 KB Output is correct
12 Correct 471 ms 67844 KB Output is correct
13 Correct 384 ms 68100 KB Output is correct
14 Correct 390 ms 68180 KB Output is correct
15 Correct 405 ms 68128 KB Output is correct
16 Correct 409 ms 68212 KB Output is correct
17 Correct 521 ms 65784 KB Output is correct

Subtask #4
0 / 51.0

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