Submission #413140

#	Time	Username	Problem	Language	Result	Execution time	Memory
413140		schse	Werewolf (IOI18_werewolf)	C++14	15 / 100	4053 ms	33184 KiB

werewolf

#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 (stderr)

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51