oj.uz

Submission #1016346

# Submission time Handle Problem Language Result Execution time Memory
1016346 2024-07-07T20:52:34 Z lacito Werewolf (IOI18_werewolf) C++14
15 / 100
 164 ms 19544 KB 
#include "werewolf.h"
using namespace std;
 
const int MAXN = 3000;
 
vector<int> g[MAXN];
vector<bool> vis1;
vector<bool> vis2;
int n, l, r;
 
void dfs(int v, bool human, vector<bool> &vis) {
  vis[v] = true;
  for (int u : g[v]) {
    if (!vis[u]) {
      if (human && u >= l || !human && u <= r) { // werewolf condition
        dfs(u, human, vis);
      }
    }
  }
}
 
 
int solve(int s, int e) {
      // check all the cities where we can transform
    vis1.assign(n, false);
    dfs(s, true, vis1);
    vis2.assign(n, false);
    dfs(e, false, vis2);
    for(int i = 0; i < vis1.size(); i++){
        if(vis1[i] && vis2[i]){
            return 1;
        }
    }
    
    return 0;
}
 
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                  vector<int> S, vector<int> E,
                                  vector<int> L, vector<int> R) {
  for (int i = 0; i < X.size(); i++) {
    // road between X[i] and Y[i]
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  n = N;
  int Q = S.size();
  vector<int> A(Q);
  for (int i = 0; i < Q; ++i) {
    l = L[i];
    r = R[i];
    A[i] = solve(S[i], E[i]);
  }
  return A;
}

Compilation message

werewolf.cpp: In function 'void dfs(int, bool, std::vector<bool>&)':
werewolf.cpp:15:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   15 |       if (human && u >= l || !human && u <= r) { // werewolf condition
      |           ~~~~~~^~~~~~~~~
werewolf.cpp: In function 'int solve(int, int)':
werewolf.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0; i < vis1.size(); i++){
      |                    ~~^~~~~~~~~~~~~
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:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int i = 0; i < X.size(); i++) {
      |                   ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 155 ms 744 KB Output is correct
11 Correct 55 ms 836 KB Output is correct
12 Correct 19 ms 856 KB Output is correct
13 Correct 164 ms 872 KB Output is correct
14 Correct 75 ms 604 KB Output is correct
15 Correct 164 ms 1008 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 19544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 155 ms 744 KB Output is correct
11 Correct 55 ms 836 KB Output is correct
12 Correct 19 ms 856 KB Output is correct
13 Correct 164 ms 872 KB Output is correct
14 Correct 75 ms 604 KB Output is correct
15 Correct 164 ms 1008 KB Output is correct
16 Runtime error 82 ms 19544 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -