oj.uz

Submission #413140

# Submission time Handle Problem Language Result Execution time Memory
413140 2021-05-28T09:27:24 Z schse Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 33184 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;

struct node
{
  bool human = false;
  bool wolf = false;
  vector<int> edges;
};
vector<node> g;

void humanfdfs(int n, int l)
{
  if (n < l || g[n].human)
    return;
  g[n].human = true;
  for (auto i : g[n].edges)
  {
    humanfdfs(i, l);
  }
}

bool wolfdfs(int n, int r)
{
  if (n > r || g[n].wolf)
    return false;
  g[n].wolf = true;
  if (g[n].wolf && g[n].human)
    return true;
  for (auto i : g[n].edges)
  {
    if (wolfdfs(i, r))
      return true;
  }
  return false;
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R)
{
  g.resize(N);
  for (int i = 0; i < X.size(); i++)
  {
    g[X[i]].edges.push_back(Y[i]);
    g[Y[i]].edges.push_back(X[i]);
  }
  vector<int> out;
  for (int i = 0; i < S.size(); i++)
  {
    humanfdfs(S[i], L[i]);
    out.push_back(wolfdfs(E[i], R[i]));

    for (int e = 0; e < N; e++)
      g[e].wolf = g[e].human = false;
  }

  return out;
}

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:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int i = 0; i < X.size(); i++)
      |                   ~~^~~~~~~~~~
werewolf.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int i = 0; i < S.size(); i++)
      |                   ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 162 ms 740 KB Output is correct
11 Correct 102 ms 724 KB Output is correct
12 Correct 22 ms 716 KB Output is correct
13 Correct 157 ms 748 KB Output is correct
14 Correct 113 ms 728 KB Output is correct
15 Correct 259 ms 904 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4053 ms 33184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 162 ms 740 KB Output is correct
11 Correct 102 ms 724 KB Output is correct
12 Correct 22 ms 716 KB Output is correct
13 Correct 157 ms 748 KB Output is correct
14 Correct 113 ms 728 KB Output is correct
15 Correct 259 ms 904 KB Output is correct
16 Execution timed out 4053 ms 33184 KB Time limit exceeded
17 Halted 0 ms 0 KB -