Submission #280487

#	Time	Username	Problem	Language	Result	Execution time	Memory
280487		cjoa	Werewolf (IOI18_werewolf)	C++11	15 / 100	4058 ms	28544 KiB

werewolf

#include "werewolf.h"

#include <queue>
#include <iostream>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

VVI G;
const int INF = 1000000000;

bool found;
VVI vis;
void dfs(int form, int u, int dst, int left, int right) {
   if (u == dst && form == 1) {
      found = true;
      return;
   }
   
   vis[form][u] = true;
   for (int v : G[u]) {
      if (form == 0) {
         // soy humano
         if (v < left) continue;
      }
      else {
         // soy werewolf
         if (v > right) continue;
      }
      if (!vis[form][v])
         dfs(form, v, dst, left, right);
   }

   if (form == 0) {
      if (left <= u && u <= right)
         if (!vis[1][u])
            dfs(1, u, dst, left, right);
   }
}

bool solve(int N, int src, int dst, int left, int right) {
   vis = VVI(2, VI(N, 0));

   found = false;
   dfs(0, src, dst, left, right);
   return found;
}

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 = VVI(N);
   int M = X.size();
   for (int j = 0; j < M; ++j) {
      int u = X[j], v = Y[j];
      G[u].push_back(v);
      G[v].push_back(u);
   }

   int Q = S.size();
   vector<int> res(Q);

   for (int i = 0; i < Q; ++i) {
      int src = S[i], dst = E[i];
      int left = L[i], right = R[i];
      res[i] = solve(N, src, dst, left, right);
   }

   return res;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51