Submission #1038860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038860		Mr_Husanboy	Werewolf (IOI18_werewolf)	C++17	0 / 100	710 ms	524288 KiB

werewolf

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

using namespace std;

#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long

template<typename T>
int len(T &a){return a.size();}

const int inf = 1e9 + 10;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

struct DSU{
  vector<int> par, sz; int n;
  DSU (int _n){
    n = _n;
    par.resize(n);
    iota(all(par), 0);
    sz.assign(n, 1);
  }
  DSU (){}
  int get(int a){
    return (par[a] == a ? a : par[a] = get(par[a]));
  }

  void init(int _n){
    n = _n;
    par.resize(n);
    iota(all(par), 0);
    sz.assign(n, 1);
  }

  void unite(int a, int b){
    a = get(a);
    b = get(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a,b);
    sz[a] += sz[b];
    par[b] = a;
  }

  void link(int a, int b){
    a = get(a); b = get(b);
    if(a == b) return;
    sz[b] += sz[a];
    par[a] = b;
  }
};

int n, m, q;
vector<vector<int>> g;
vector<int> line;

void dfs(int i, int p = -1){
  line.push_back(i);
  for(auto u : g[i]){
    if(u != p) dfs(u, i);
  }
}

struct Sparsemin{
  int n, logn;
  vector<vector<int>> t;
  Sparsemin (){}
  void init(int _n){
    n = _n;
    logn = 32 - __builtin_clz(n);
    t.assign(logn, vector<int> (n));
  }

  int merge(int a, int b){
    return min(a, b);
  }

  void build(vector<int> &a){    
    init(len(a));
    //cout << n << endl;
    for(int i = 0; i < n; i ++) t[0][i] = a[i];
    for(int j = 1; j < logn; j ++){
      for(int i = 0; i + (1 << j) - 1 < n; i ++){
        t[j][i] = merge(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  int get(int l, int r){
    if(l > r) return inf;
    int k = 31 - __builtin_clz(r - l + 1);
    return merge(t[k][l], t[k][r - (1 << k) + 1]);
  }
};


struct Sparsemax{
  int n, logn;
  vector<vector<int>> t;
  Sparsemax (){}
  void init(int _n){
    n = _n;
    logn = 32 - __builtin_clz(n);
    t.assign(logn, vector<int> (n));
  }

  int merge(int a, int b){
    return max(a, b);
  }

  void build(vector<int> &a){
    init(len(a));
    //cout<< n << endl;
    for(int i = 0; i < n; i ++) t[0][i] = a[i];
    for(int j = 1; j < logn; j ++){
      for(int i = 0; i + (1 << j) - 1 < n; i ++){
        t[j][i] = merge(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  int get(int l, int r){
    if(l > r) return -inf;
    int k = 31 - __builtin_clz(r - l + 1);
    return merge(t[k][l], t[k][r - (1 << k) + 1]);
  }
};



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;
  q = len(s);
  m = len(x);
  vector<int> res(q);
  g.resize(n);
  for(int i = 0; i < m; i ++){
    g[x[i]].push_back(y[i]);
    g[y[i]].push_back(x[i]);
  }

  int mn = 0;
  for(int i = 1; i < n; i++) if(len(g[i]) == 1) mn = i;
  dfs(mn);

  Sparsemin hum; Sparsemax wolf;  
  hum.build(line); wolf.build(line);
  vector<int> pos(n);
  for(int i = 0; i < n; i++) pos[line[i]] = i;
  for(int i = 0; i < q; i ++){
    s[i] = pos[s[i]];
    e[i] = pos[e[i]];
    int lb = -1, rb = s[i];
    while(rb - lb > 1){
      int mid = (lb + rb) / 2;
      if(hum.get(mid, s[i]) < l[i]){
        lb = mid;
      }else rb = mid;
    }
    int hl = rb;
    lb = s[i], rb = n;
    while(rb - lb > 1){
      int mid = (lb + rb) / 2;
      if(hum.get(s[i], mid) < l[i]){
        rb = mid;
      }else lb = mid;
    }
    int hr = lb;

    lb = -1, rb = e[i];

    while(rb - lb > 1){
      int mid = (lb + rb) / 2;
      if(wolf.get(mid, e[i]) > r[i]){
        lb = mid;
      }else rb = mid;
    }
    int wl = rb;
    lb = -1, rb = e[i];
    while(rb - lb > 1){
      int mid = (lb + rb) / 2;
      if(wolf.get(e[i], mid) > r[i]){
        rb = mid;
      }else lb = mid;
    }
    int wr = lb;
    //cout << hl << ' ' << hr << endl;
    res[i] = not(wl > hr || hl > wr);
  }
  return res;
}

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