Submission #1195796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195796		madamadam3	Werewolf (IOI18_werewolf)	C++20	0 / 100	4094 ms	47440 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))

typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;

/*
  N = num nodes
  X, Y = edges
  S, E = start and end nodes
  L, R = human and werewolf cities
*/

int n, m, q;
vi x, y, s, e, l, r;
vector<vi> adj;

bool dfs(int u, int L, int R, int target, vector<bool> &seen, bool reached_transform, bool reached_vampire) {
  // cout << "At node " << u << " L, R = (" << L << ", " << R << ") target = " << target << " RT? " << reached_transform << " RV? " << reached_vampire << "\n"; 
  if (u == target) {
    // cout << "Reached " << target << " did we transform? " << reached_transform << "\n";
    return reached_transform;
  }

  bool can = false;
  seen[u] = true;

  for (auto v : adj[u]) {
    if (seen[v]) continue;
    if (reached_vampire && v > R) continue;
    if (!reached_transform && v < L) continue;

    bool nt = reached_transform || (v >= L && v <= R);
    bool nv = reached_vampire || (v < L);
    can = can || dfs(v, L, R, target, seen, nt, nv);
    if (can) break;
  }

  seen[u] = false;
  return can;
}

int answer_query(int qn) {
  // cout << "answering query " << qn << "\n";
  int start = s[qn], end = e[qn];
  vector<bool> seen(n, false);

  return dfs(start, l[qn], r[qn], end, seen, start >= l[qn] && start <= r[qn], start < l[qn]);
}

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
  n = N; x = X; y = Y; s = S; e = E; l = L; r = R;
  m = x.size(), q = S.size();
  
  adj.assign(n, vi());
  FOR(i, 0, m) {
    adj[X[i]].pb(Y[i]);
    adj[Y[i]].pb(X[i]);
  }

  vi A(q);
  
  for (int i = 0; i < q; ++i) {
    A[i] = answer_query(i);
  }

  return A;
}

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