Submission #1195916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195916		madamadam3	Werewolf (IOI18_werewolf)	C++20	0 / 100	4096 ms	96624 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>;

struct DSU {
  int n;
  vi par, siz, fchange;
  vector<set<int>> has;
  int timer = 0;
  // vi left, right;

  DSU(int n) {
    par.assign(n, 0); iota(all(par), 0);
    siz.assign(n, 1);
    fchange.assign(n, INT_MAX);
    has.assign(n, set<int>());
    FOR(i, 0, n) has[i].insert(i);
    // left.assign(n, 1); iota(all(left), 0);
    // right.assign(n, 1); iota(all(right), 0); 
  }

  int find_set(int v, int time) {
    if (fchange[v] > time || par[v] == v) return v;
    // return par[v] = find_set(par[v]);
    return find_set(par[v], time);
  }

  void union_set(int a, int b) {
    a = find_set(a, timer);
    b = find_set(b, timer);
    if (a != b) {
      // if (siz[b] > siz[a]) swap(a, b);
      par[b] = a;
      siz[a] += siz[b];
      fchange[b] = timer++;
      if (has[b] > has[a]) swap(has[b], has[a]);
      has[a].insert(all(has[b]));

      // left[a] = min(left[a], left[b]);
      // right[a] = min(right[a], right[b]);
    }
  }
};

/*
  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;
vi queries;
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]);
}

void dfs_dp(int u, int p, vi &DP) {
  DP[u] = u;

  for (auto &v : adj[u]) {
    if (v == p) continue;
    dfs_dp(v, u, DP);
    DP[u] = max(DP[u], DP[v]);
  }
}

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]);
  }

  queries.assign(q, 0); iota(all(queries), 0);
  // sort(all(queries), [&](int a, int b) {return L[a] > L[b];});

  vi A(q);
  
  auto blueDSU = DSU(n);
  auto redDSU = DSU(n);
  vi wB(m), wR(m); iota(all(wB), 0); iota(all(wR), 0);
  FOR(i, 0, m) {
    wR[i] = max(X[i], Y[i]);
    wB[i] = min(X[i], Y[i]);
  }

  sort(all(wR), [&](int a, int b) {return max(X[a], Y[a]) < max(X[b], Y[b]);}); 
  sort(all(wB), [&](int a, int b) {return min(X[a], Y[a]) < min(X[b], Y[b]);}); reverse(all(wB));

  for (auto &edge : wR) {
    redDSU.union_set(X[edge], Y[edge]);
  }

  for (auto &edge : wB) {
    blueDSU.union_set(X[edge], Y[edge]);
  }

  /*
    line case:
    process queries in decreasing order of L[i]
    blueDSU 
  */
  // vi pthmax(n, INT_MIN);
  // dfs_dp(0, 0, pthmax);
  int curedge = 0;

  // for (auto query : queries) {
    // int cidx = wB[curedge];
    // while (min(X[cidx], Y[cidx]) >= L[query]) {
    //   blueDSU.union_set(X[cidx], Y[cidx]);
    //   curedge++;
    //   cidx = wB[curedge];
    // }

    // tried:
    //[1, 3, 5, 7]
    // int en = E[query]; // 1
    // int en = S[query]; // 2
    // int sn = E[query]; // 3
    // int sn = S[query]; // 4
    // int et = L[query]; // 5
    // int et = R[query]; // 6
    // int st = L[query]; // 7
    // int st = R[query]; // 8

    // for (auto en : {E, S}) {
    // for (auto sn : {E, S}) {
    // for (auto et : {L, R}) {
    // for (auto st : {L, R}) {
    // for (auto query : queries) {
    FOR(query, 0, q) {
      auto en = E;
      auto sn = S;
      auto et = R;
      auto st = L;
      set<int> s1 = redDSU.has[redDSU.find_set(en[query], et[query])];
      set<int> s2 = blueDSU.has[blueDSU.find_set(sn[query], st[query])];
      bool found = false;
      for (auto &el : s1) {
        if (s2.count(el)) {
          // cout << "1\n";
          // found = true;
          A[query] = 1;
          break;
        }
      }
      // if (!found) cout << "0\n";
    }
      // cout << "\n";
    // }}}}
  // }

  FOR(i, 0, q) A[i] = 1 - A[i];
  return A;
}

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