Submission #1181124

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181124		Nailuj_217	Werewolf (IOI18_werewolf)	C++20	15 / 100	4098 ms	81072 KiB

werewolf

/*

Works, but to slow because of need for specific merge in the union find, which can be exploited

*/

#include <bits/stdc++.h>
#define ll long long
using namespace std;

#ifdef EVAL
#include "werewolf.h"
#else
#include "grader.cpp"
#endif

struct Query {
  ll start, end;
  ll low, high;
  ll index;

  Query(ll start, ll end, ll low, ll high, ll index) : start(start), end(end), low(low), high(high), index(index) {}
};

const ll LEN = 200005;

array<vector<ll>, LEN> adj;
array<vector<ll>, LEN> new_adj;
vector<Query> queries;
array<ll, LEN> sz;
array<pair<ll, ll>, LEN> parent;
array<vector<ll>, LEN> children;
array<pair<ll, ll>, LEN> range;
array<ll, LEN> translator;
array<ll, LEN> back_translator;

array<ll, LEN> new_parent;  
array<set<ll>, LEN> new_nodes;

void insert(ll i) {
  parent[i] = {i, -1};
  sz[i] = 1;
}

void insert_new(ll i) {
  new_parent[i] = i;
  new_nodes[i].insert(i);
}

ll get_parent_new(ll i) {
  if (new_parent[i] == i) return i;
  return new_parent[i] = get_parent_new(new_parent[i]);
}

void merge_new(ll a, ll b) {
  if (new_parent[a] == -1 || new_parent[b] == -1) return;
  a = get_parent_new(a);
  b = get_parent_new(b);
  if (new_nodes[b].size() > new_nodes[a].size()) swap(a, b);
  new_parent[b] = a;
  new_nodes[a].merge(new_nodes[b]);
}

ll get_parent(ll i, ll threshold = 1e18) {
  if (parent[i].first == i || parent[i].second > threshold) return i;
  return get_parent(parent[i].first, threshold);
}

void merge_sets(ll a, ll b, ll threshold) {
  if (parent[a].first == -1 || parent[b].first == -1) return;
  a = get_parent(a);
  b = get_parent(b);
  if (a == b) return;
  if (a < b) swap(a, b);
  parent[b] = {a, threshold};
  children[a].push_back(b);
  sz[a] += sz[b];
}

ll from_pos(ll i, ll index) {
  index++;
  translator[i] = index;
  back_translator[index] = i;
  range[index].first = index;
  for (auto c: children[i]) {
    index = from_pos(c, index);
  }
  range[translator[i]].second = index;
  return index;
}



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)
{
  ll n = N;

  for (int i = 0; i < X.size(); i++) {
    adj[X[i]].push_back(Y[i]);
    adj[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < S.size(); i++) {
    queries.push_back(Query(S[i], E[i], L[i], R[i], i));
  }
  parent.fill({-1, -1});
  for (int i = 0; i < n; i++) {
    insert(i);
    for (auto a: adj[i]) {
      merge_sets(i, a, i);
    }
  }
  from_pos(get_parent(0), -1);
  new_parent.fill(-1);
  for (int i = 0; i < n; i++) {
    for (auto a: adj[i]) {
      new_adj[translator[i]].push_back(translator[a]);
    }
  }

  sort(queries.begin(), queries.end(), [](Query &a, Query &b) {
    return a.low < b.low;
  });

  vector<int> sol(queries.size(), 0);
  // loop from top over all queries
  Query query = {0, 0, 0, 0, 0};
  pair<ll, ll> rg;
  ll c1, c2, c3;
  for (int i = n - 1; i >= 0; i--) {
    insert_new(translator[i]);
    for (auto a: new_adj[translator[i]]) {
      merge_new(translator[i], a);
    }
    /*
    
      Human(high pop. areas) -> Werewolf(low pop. areas)
    
    */

    while (queries.size() && queries.back().low == i) {
      query = queries.back(); queries.pop_back();

      // set of new nodes for when still a human (so only high populated areas)
      c1 = get_parent_new(translator[query.start]);
      // new nodes set
      set<ll> &nodes = new_nodes[c1];

      // range for while a werewolf (so only low populated areas)
      c1 = get_parent(query.end, query.high);
      // new nodes range
      rg = range[translator[c1]];

      auto it = nodes.lower_bound(rg.first);
      if (it == nodes.end()) continue;
      else if (*it <= rg.second) sol[query.index] = 1;
    }
  }

  return sol;
}
/*
6 6 3
0 3 
3 4 
3 1
1 2
2 5
5 1
4 2 1 2
4 2 2 2
5 4 3 4




*/

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