Submission #1186098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186098		hamzabc	Werewolf (IOI18_werewolf)	C++20	100 / 100	3924 ms	289012 KiB

werewolf

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


using namespace std;
#define all(x) x.begin(), x.end()
#define sp << " " <<


struct node{
  int next;
  int limit;
  int sblen = 1;
};


vector<node> DSUhuman, DSUwarewolf;


int goDSU(int a, int limit, vector<node> &DSU){
  if (DSU[a].next == a || DSU[a].limit > limit){
    return a;
  }
  return goDSU(DSU[a].next, limit, DSU);
}

void merge(int a, int b, int limit, vector<node> &DSU){
  a = goDSU(a, 1e9, DSU);
  b = goDSU(b, 1e9, DSU);
  if (a == b)
    return;
  if (DSU[a].sblen > DSU[b].sblen)
    swap(a, b);
  if (DSU[a].sblen == DSU[b].sblen){
    DSU[b].sblen++;
  }
  DSU[a].limit = limit;
  DSU[a].next = b;
}


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) {
  int Q = S.size(), M = X.size();
  std::vector<int> A(Q);
  vector<vector<int>> graph(N);
  DSUhuman.resize(N);
  DSUwarewolf.resize(N);
  for (int i = 0; i < M; i++){
    graph[X[i]].push_back(Y[i]);
    graph[Y[i]].push_back(X[i]);
  }
  for (int i = 0; i < N; i++){
    DSUhuman[i].next = i;
    DSUwarewolf[i].next = i;
  }
  for (int i = 0; i < N; i++){
    for (auto go : graph[i]){
      if (go < i){
        merge(i, go, i, DSUwarewolf);
      }
    }
  }
  for (int i = N - 1; i >= 0; i--){
    for (auto go : graph[i]){
      if (go > i){
        merge(i, go, N - i - 1, DSUhuman);
      }
    }
  }
  vector<array<int, 4>> road; // warewolflimit, humanlimit, source, end;
  for (int i = 1; i < N - 1; i++){
    int a = goDSU(i, i, DSUwarewolf), b = goDSU(i, N - 1 - i, DSUhuman), l1 = i, l2 = N - 1 - i, p = 0;
    while (true){
      p = b;
      l2 = N - 1 - i;
      while (true){
        road.push_back({ l1, l2, p, a });
        l2 = DSUhuman[p].limit;
        if (DSUhuman[p].next == p){
          break;
        }
        p = goDSU(p, l2, DSUhuman);
      }
      l1 = DSUwarewolf[a].limit;
      if (DSUwarewolf[a].next == a){
        break;
      }
      a = goDSU(a, l1, DSUwarewolf);
    }
  }
  sort(all(road));
  vector<int> out(Q);
  vector<array<int, 5>> querys(Q);
  for (int i = 0; i < Q; i++){
    if (R[i] == N - 1 || L[i] == 0){
      out[i] = 1;
    }else{
      querys[i][0] = R[i];
      querys[i][1] = N - 1 - L[i];
      querys[i][2] = goDSU(S[i], N - 1 - L[i], DSUhuman);
      querys[i][3] = goDSU(E[i], R[i], DSUwarewolf);
      querys[i][4] = i;
    }
  }
  sort(all(querys));
  int j = 0;
  map<pair<int, int>, int> mp;
  for (int i = 0; i < querys.size(); i++){
    while (j < road.size() && road[j][0] <= querys[i][0]){
      if (mp[{ road[j][2], road[j][3] }]){
        mp[{ road[j][2], road[j][3] }] = min(road[j][1], mp[{ road[j][2], road[j][3] }]);
      }else{
        mp[{ road[j][2], road[j][3] }] = road[j][1];
      }
      j++;
    }
    if (mp[{ querys[i][2], querys[i][3] }] && mp[{ querys[i][2], querys[i][3] }] <= querys[i][1]){
      out[querys[i][4]] = 1;
    }
  }
  return out;
}

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