Submission #531237

#	Time	Username	Problem	Language	Result	Execution time	Memory
531237		cadmiumsky	Werewolf (IOI18_werewolf)	C++14	100 / 100	2121 ms	321048 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int nmax = 2e5 + 5;
#define tree asdhgasdgjahsd
struct DSU {
  vector<int> dsu;
  vector<vector<int> > tree;
  vector< vector<int> > p;
  vector<int> pin, pout;
  int inp = 0;
  vector<int> preord;
  bool cond;
  void init(int n, bool c) {
    dsu.resize(n);
    pin.resize(n);
    pout.resize(n);
    tree.resize(n, vector<int>());
    p.resize(n, vector<int>(18,0));
    cond = c;
    for(int i = 0; i < n; i++)
      dsu[i] = i;
  }
  int father(int x) {
    return (dsu[x] == x? x : father(dsu[x] = father(dsu[dsu[x]]))); 
  }
  void push(int u, int v) { 
    v = father(v);
    if(v == u)
      return;
    p[v][0] = u;
    tree[u].push_back(v);
    dsu[v] = u;
  }
  void dfs(int node) {
    preord.push_back(node);
    pin[node] = inp++;
    for(int i = 1; i < 18; ++i)
      p[node][i] = p[p[node][i - 1]][i - 1];
    for(auto x : tree[node])
      dfs(x);
    pout[node] = inp - 1;
  }
  int r;
  vector<int> init(int root) {
    p[root][0] = root;
    dfs(root);
    r = root;
    return preord;
  }
  bool isanc(int f, int node) {
    return pin[f] <= pin[node] && pout[node] <= pout[f];
  }
  pair<int,int> findbest(int start, int limit) {
    for(int i = 17; i >= 0; i--) {
      if(((p[start][i] < limit) ^ cond) || p[start][i] == limit)
        start = p[start][i];
    }
    return {pin[start], pout[start]};
  }
};
int n, m, q;

vector<int> g[nmax];
vector<int> v;
namespace AINT {
  set<int> aint[nmax * 4];
  void construct(int node = 1, int cl = 0, int cr = n - 1) {
    if(cl == cr) {
      aint[node].insert(v[cl]);
      return;
    }
    int mid = cl + cr >> 1;
    construct(2 * node, cl, mid);
    construct(2 * node + 1, mid + 1, cr);
    for(auto x : aint[2 * node])
      aint[node].insert(x);
    for(auto x : aint[2 * node + 1])
      aint[node].insert(x);
    return;
  }
  bool query(int l, int r, int liml, int limr, int node = 1, int cl = 0, int cr = n - 1) {
    if(cr < l || r < cl)
      return 0;
    if(l <= cl && cr <= r) {
      //cout <<"! " <<l <<' '<< cl << ' ' << cr << ' '<< r << '\t' << liml << ' ' << *aint[node].lower_bound(liml) <<' ' << limr << '\n';
      auto it = aint[node].lower_bound(liml);
      return (it != aint[node].end() &&(*it) <= limr);
    }
    int mid = cl + cr >> 1;
    return query(l, r, liml, limr, 2 * node, cl, mid) ||
           query(l, r, liml, limr, 2 * node + 1, mid + 1, cr);
  }
};

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) {
  n = N;
  m = X.size();
  q = l.size();
  DSU lower;
  DSU upper;
  lower.init(n ,0);
  upper.init(n ,1);
  for(int i = 0; i < m; i++) {
    g[X[i]].push_back(Y[i]);
    g[Y[i]].push_back(X[i]);
  }
  for(int i = 0; i < n; i++) {
    for(auto x : g[i])
      if(x <= i)
        lower.push(i, x);
  }
  for(int i = n - 1; i >= 0; i--) {
    for(auto x : g[i])
      if(x >= i)
        upper.push(i, x);
  }
  vector<int> down = lower.init(n - 1), up = upper.init(0), inv(n);

  v.resize(n);
  for(int i = 0; i < n; i++) {
    inv[up[i]] = i;
  }
  for(int i = 0; i < n; i++)
    v[i] = inv[down[i]];
  AINT::construct();
  vector<int> sol(q, 0);
  for(int i = 0, cl, cr, liml, limr; i < q; i++) {
    swap(s[i], e[i]);
    tie(cl, cr) = lower.findbest(s[i], r[i]);
    tie(liml, limr) = upper.findbest(e[i], l[i]);
    sol[i] = AINT::query(cl, cr, liml, limr);
  }
  return sol;
}

Compilation message (stderr)

werewolf.cpp: In function 'void AINT::construct(int, int, int)':
werewolf.cpp:73:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
werewolf.cpp: In function 'bool AINT::query(int, int, int, int, int, int, int)':
werewolf.cpp:90:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |     int mid = cl + cr >> 1;
      |               ~~~^~~~

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