oj.uz

답안 #1016337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016337 2024-07-07T20:20:22 Z lacito 늑대인간 (IOI18_werewolf) C++14
7 / 100
 4000 ms 27988 KB 
#include "werewolf.h"
using namespace std;

const int MAXN = 3000;

vector<int> g[MAXN];
vector<bool> vis;
int n, l, r;

void dfs(int v, bool human) {
  vis[v] = true;
  for (int u : g[v]) {
    if (!vis[u]) {
      if (human && u >= l || !human && u <= r) { // werewolf condition
        dfs(u, human);
      }
    }
  }
}


int solve(int s, int e) {
  // check all the cities where we can transform
  for (int i = l; i <= r; i++) {
    vis.assign(n, false);
    dfs(i, true);
    if (vis[s]) {
      vis.assign(n, false);
      dfs(i, false);
      if (vis[e]) 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)':
werewolf.cpp:14:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   14 |       if (human && u >= l || !human && u <= r) { // werewolf condition
      |           ~~~~~~^~~~~~~~~
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:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (int i = 0; i < X.size(); i++) {
      |                   ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Execution timed out 4062 ms 860 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 81 ms 27988 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Execution timed out 4062 ms 860 KB Time limit exceeded
11 Halted 0 ms 0 KB -