Submission #825999

#	Time	Username	Problem	Language	Result	Execution time	Memory
825999		thimote75	Werewolf (IOI18_werewolf)	C++14	15 / 100	4050 ms	52240 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

struct Road {
  int x, y;

  Road (int _x, int _y) {
    x = min(_x, _y);
    y = max(_x, _y);
  }
};

using t_Roads = vector<Road>;
using t_Graph = vector<t_Roads>;

t_Graph roads;
igrid visited; int stage = 0;

bool dfs (int source, int state, int target, int left, int right) {
    if (state >= 2)
      return false;
    if (state == 0 && source < left) return false;
    if (state == 1 && source > right) return false;

    if (source == target) return true;

    
    if (visited[source][state] == stage) return false;
    visited[source][state] = stage;

    for (Road &road : roads[source]) {
        int next = road.x == source ? road.y : road.x;

        if (road.x < left && right < road.y) continue ;
        
        if (dfs(next, state,     target, left, right)
         || dfs(next, state + 1, target, left, right))
            return true;
    }

    return false;
}

idata check_validity(int N, idata X, idata Y,
                            idata S, idata E,
                            idata L, idata R) {
  int M = X.size(); int Q = S.size();

  roads.resize(N);

  for (int i = 0; i < M; i ++) {
    Road road (X[i], Y[i]);

    roads[road.x].push_back(road);
    roads[road.y].push_back(road);
  }

  idata A(Q);
  visited.resize(N, idata(2));

  for (int i = 0; i < Q; i ++) {
    stage ++;
    A[i] = dfs(S[i], 0, E[i], L[i], R[i]);
  }

  return A;
}

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