Submission #825975

#	Time	Username	Problem	Language	Result	Execution time	Memory
825975		thimote75	Werewolf (IOI18_werewolf)	C++14	0 / 100	3976 ms	39816 KiB

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;

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;
idata visited; int stage = 0;

bool dfs (int source, int target, int left, int right) {
    if (source == target) return true;
    
    if (visited[source] == stage) return false;
    visited[source] = stage;

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

        if (road.x <  left && right  < road.y) continue ;
        if (next   >= left && source < left) continue ;
        
        if (dfs(next, 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);

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

  return A;
}

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