Submission #321592

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321592	2020-11-12T19:58:26 Z	VROOM_VARUN	Werewolf (IOI18_werewolf)	C++14	100 / 100	1485 ms	152976 KB

werewolf

/*
ID: varunra2
LANG: C++
TASK: werewolf
*/

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

#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
  cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif

#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second

const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions

int n, m, q;

const int bits = 20;

struct BIT {
  VI bit;
  int n;
  void init(int _n) {
    n = _n;
    bit.resize(n + 1);
  }

  void upd(int ind) {
    ind++;
    while (ind <= n) {
      bit[ind]++;
      ind += (ind & -ind);
    }
  }

  int qry(int ind) {
    int ret = 0;
    ind++;
    while (ind >= 1) {
      ret += bit[ind];
      ind -= (ind & (-ind));
    }
    return ret;
  }

  int qry(int l, int r) { return qry(r) - qry(l - 1); }
} sweep;

struct dsu {
  VI par;
  VI siz;
  VI treepar;

  void init(int n) {
    par.resize(n);
    treepar.resize(n);
    iota(all(par), 0);
    iota(all(treepar), 0);
  }

  int find(int x) {
    if (x != par[x]) return par[x] = find(par[x]);
    return x;
  }

  bool same(int x, int y) { return find(x) == find(y); }

  bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    // ok so how are we going to calculate treepar
    treepar[y] = x;
    par[y] = x;
    return true;
  }
};

struct tree {
  VII edgs;
  dsu dsu1;
  VI par;
  VVI lca;
  int root;
  VVI child;
  vector<bool> seen;
  VI sub;
  VI l;
  VI r;
  VI ord;
  int time = 0;

  void genchild() {
    for (int i = 0; i < m; i++) {
      int u = edgs[i].x;
      int v = edgs[i].y;
      dsu1.merge(u, v);
    }
    for (int i = 0; i < n; i++) {
      if (dsu1.treepar[i] == i) continue;
      child[dsu1.treepar[i]].PB(i);
    }
  }

  void dfslca(int u, int v) {
    lca[u][0] = v;
    for (int i = 1; i < bits; i++) {
      int to = lca[u][i - 1];
      if (to == -1)
        lca[u][i] = -1;
      else
        lca[u][i] = lca[to][i - 1];
    }
    for (auto& x : child[u]) {
      dfslca(x, u);
    }
  }

  void dfsord(int u, int v) {
    sub[u] = 1;
    l[u] = sz(ord);
    ord.PB(u);
    for (auto& x : child[u]) {
      dfsord(x, u);
      sub[u] += sub[x];
    }
    r[u] = l[u] + sub[u] - 1;
  }

  void genLCA() {
    root = edgs.back().x;
    dfslca(root, -1);
  }

  void genOrd() { dfsord(root, -1); }

  void init(int n, VII _edgs) {
    edgs = _edgs;
    dsu1.init(n);
    lca.resize(n);
    par.assign(n, -1);
    seen.assign(n, false);
    child.resize(n);
    sub.resize(n);
    l.resize(n);
    r.resize(n);
    for (int i = 0; i < n; i++) {
      lca[i].resize(bits);
    }
    genchild();
    genLCA();
    genOrd();
  }
} human, wolf;

VI check_validity(int _n, VI x, VI y, VI s, VI e, VI l, VI r) {
  n = _n;
  q = sz(s);
  m = sz(x);

  VII edghu(m), edgwo(m);
  for (int i = 0; i < m; i++) {
    int u = x[i];
    int v = y[i];
    if (u > v) swap(u, v);
    edghu[i] = MP(u, v);
    edgwo[i] = MP(v, u);
  }

  sort(all(edghu));
  reverse(all(edghu));
  sort(all(edgwo));

  human.init(n, edghu);

  wolf.init(n, edgwo);

  VI l1(q), r1(q);
  VI l2(q), r2(q);

  VI ret(q, 0);
  VII qrys(q, MP(0, 0));

  for (int i = 0; i < q; i++) {
    // for human get the last ancestor of s[i] that is >= l[i]
    int u = s[i], v = e[i];

    int ll = l[i], rr = r[i];
    // first we will do human
    for (int j = bits - 1; j >= 0; j--) {
      int to = human.lca[u][j];
      if (to == -1) continue;
      if (to >= ll) u = to;
    }

    for (int j = bits - 1; j >= 0; j--) {
      int to = wolf.lca[v][j];
      if (to == -1) continue;
      if (to <= rr) v = to;
    }

    // so the ancestor for the human tree is u
    // so the ancestor for the wolf tree is v

    if (s[i] < ll or e[i] > rr) ret[i] = -1;
    l1[i] = human.l[u];
    r1[i] = human.r[u];
    l2[i] = wolf.l[v];
    r2[i] = wolf.r[v];
  }

  // now we need to relabel the nodes

  VI perm1(n);  // holds what index each node is at

  for (int i = 0; i < n; i++) {
    perm1[human.ord[i]] = i;
  }

  VI perm2(n);

  for (int i = 0; i < n; i++) {
    perm2[perm1[wolf.ord[i]]] = i;
  }

  // now we need to make the sweep stuff
  VVI events;
  // we have three types of events
  // a) insert an element
  // b) first query of a range
  //      store: time, type, qry idx, left bound, right bound
  // c) second query of a range after you have inserted elements into range
  //      store: time, type, qry idx, left bound, right bound

  // first we will add all the updates;

  for (int i = 0; i < n; i++) {
    VI cur;
    cur = {i, 0};
    events.PB(cur);
  }

  for (int i = 0; i < q; i++) {
    VI cur1;
    VI cur2;
    cur1 = {l1[i] - 1, 1, i, l2[i], r2[i]};
    cur2 = {r1[i], 2, i, l2[i], r2[i]};
    events.PB(cur1);
    events.PB(cur2);
  }
  sort(all(events));

  sweep.init(n);

  for (auto& x : events) {
    int type = x[1];
    if (type == 0) {
      sweep.upd(perm2[x[0]]);
    }
    if (type == 1) {
      qrys[x[2]].x = sweep.qry(x[3], x[4]);
    }
    if (type == 2) {
      qrys[x[2]].y = sweep.qry(x[3], x[4]);
    }
  }

  for (int i = 0; i < q; i++) {
    if (ret[i] == -1) {
      ret[i] = 0;
      continue;
    }
    if (qrys[i].y > qrys[i].x)
      ret[i] = 1;
    else
      ret[i] = 0;
  }

  return ret;
}

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	376 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct

Subtask #2

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	376 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	13 ms	2540 KB	Output is correct
11	Correct	12 ms	2540 KB	Output is correct
12	Correct	9 ms	2540 KB	Output is correct
13	Correct	10 ms	2668 KB	Output is correct
14	Correct	9 ms	2668 KB	Output is correct
15	Correct	11 ms	2796 KB	Output is correct

Subtask #3

34.0 / 34.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1118 ms	139936 KB	Output is correct
2	Correct	1318 ms	143416 KB	Output is correct
3	Correct	1154 ms	141152 KB	Output is correct
4	Correct	1006 ms	140320 KB	Output is correct
5	Correct	1004 ms	140224 KB	Output is correct
6	Correct	1073 ms	140068 KB	Output is correct
7	Correct	1078 ms	140224 KB	Output is correct
8	Correct	1241 ms	143536 KB	Output is correct
9	Correct	919 ms	141112 KB	Output is correct
10	Correct	877 ms	140324 KB	Output is correct
11	Correct	885 ms	139968 KB	Output is correct
12	Correct	1004 ms	140076 KB	Output is correct
13	Correct	1319 ms	148804 KB	Output is correct
14	Correct	1341 ms	148772 KB	Output is correct
15	Correct	1347 ms	148752 KB	Output is correct
16	Correct	1321 ms	148784 KB	Output is correct
17	Correct	1119 ms	139828 KB	Output is correct

Subtask #4

51.0 / 51.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	376 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	13 ms	2540 KB	Output is correct
11	Correct	12 ms	2540 KB	Output is correct
12	Correct	9 ms	2540 KB	Output is correct
13	Correct	10 ms	2668 KB	Output is correct
14	Correct	9 ms	2668 KB	Output is correct
15	Correct	11 ms	2796 KB	Output is correct
16	Correct	1118 ms	139936 KB	Output is correct
17	Correct	1318 ms	143416 KB	Output is correct
18	Correct	1154 ms	141152 KB	Output is correct
19	Correct	1006 ms	140320 KB	Output is correct
20	Correct	1004 ms	140224 KB	Output is correct
21	Correct	1073 ms	140068 KB	Output is correct
22	Correct	1078 ms	140224 KB	Output is correct
23	Correct	1241 ms	143536 KB	Output is correct
24	Correct	919 ms	141112 KB	Output is correct
25	Correct	877 ms	140324 KB	Output is correct
26	Correct	885 ms	139968 KB	Output is correct
27	Correct	1004 ms	140076 KB	Output is correct
28	Correct	1319 ms	148804 KB	Output is correct
29	Correct	1341 ms	148772 KB	Output is correct
30	Correct	1347 ms	148752 KB	Output is correct
31	Correct	1321 ms	148784 KB	Output is correct
32	Correct	1119 ms	139828 KB	Output is correct
33	Correct	1303 ms	140060 KB	Output is correct
34	Correct	628 ms	53556 KB	Output is correct
35	Correct	1423 ms	143124 KB	Output is correct
36	Correct	1171 ms	140688 KB	Output is correct
37	Correct	1328 ms	142176 KB	Output is correct
38	Correct	1250 ms	141372 KB	Output is correct
39	Correct	1222 ms	150508 KB	Output is correct
40	Correct	1435 ms	152976 KB	Output is correct
41	Correct	1244 ms	141552 KB	Output is correct
42	Correct	976 ms	140676 KB	Output is correct
43	Correct	1485 ms	149652 KB	Output is correct
44	Correct	1315 ms	142172 KB	Output is correct
45	Correct	1146 ms	150932 KB	Output is correct
46	Correct	1193 ms	150436 KB	Output is correct
47	Correct	1357 ms	149028 KB	Output is correct
48	Correct	1361 ms	148800 KB	Output is correct
49	Correct	1355 ms	149008 KB	Output is correct
50	Correct	1341 ms	148788 KB	Output is correct
51	Correct	1401 ms	152228 KB	Output is correct
52	Correct	1406 ms	152220 KB	Output is correct