Submission #280476

#	Time	Username	Problem	Language	Result	Execution time	Memory
280476		cjoa	Werewolf (IOI18_werewolf)	C++11	15 / 100	4070 ms	46188 KiB

werewolf

#include "werewolf.h"

#include <queue>
#include <iostream>

using namespace std;

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

VVI G;
struct State {
   int form; // 0=human   1=werewolf
   int city;
};

const int INF = 1000000000;
bool solve(int N, int src, int dst, int left, int right) {
   VVI GG[2];
   GG[0] = G;   // human
   GG[1] = G;   // werewolf

   queue<State> q;
   q.push({0, src});

   VVI D(2, VI(N, INF));
   D[0][src] = 0;

   while (!q.empty()) {
      State cur = q.front(); q.pop();
      if (cur.city == dst && cur.form == 1) {
         return true;
      }

      // avanzar a la siguiente ciudad
      for (int v : GG[cur.form][cur.city]) {
         if (cur.form == 0) {
            // soy humano
            if (v < left) continue;
         }
         else {
            // soy werewolf
            if (v > right) continue;
         }

         State nxt = {cur.form, v};

         if (D[nxt.form][nxt.city] > D[cur.form][cur.city] + 1) {  // si no esta visitado en el BFS
            D[nxt.form][nxt.city] = D[cur.form][cur.city] + 1;
            q.push(nxt);
         }
      }
      
      // transformacion en la ciudad actual: human => werewolf
      if (cur.form == 0) {
         if (left <= cur.city && cur.city <= right) {
            State nxt = {1, cur.city};
            if (D[nxt.form][nxt.city] > D[cur.form][cur.city] + 1) {  // si no esta visitado en el BFS
               D[nxt.form][nxt.city] = D[cur.form][cur.city] + 1;
               q.push(nxt);
            }
         }
      }
   }

   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 = 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