oj.uz

Submission #321589

# Submission time Handle Problem Language Result Execution time Memory
321589 2020-11-12T19:55:46 Z VROOM_VARUN Werewolf (IOI18_werewolf) C++14
100 / 100
 1456 ms 164300 KB 
/*
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();
  }

  void deb() {
    debug("debuginggggggggggggggggggggggggggg");
    debug(child);
    debug(ord);
  }

} 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);

  // debug("here initted human and wolf tree");

  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];
  }

  debug(l1);
  debug(r1);
  debug(s);
  debug(l);

  // now we need to relabel the nodes

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

  human.deb();

  debug(l2);
  debug(r2);
  debug(e);
  debug(r);

  wolf.deb();

  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]);
    }
  }

  debug(perm1);
  debug(perm2);

  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;
  }

  debug(qrys);

  debug("debugging events");

  trav(x, events) debug(x);

  return ret;
}

Compilation message

werewolf.cpp: In member function 'void tree::deb()':
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:195:5: note: in expansion of macro 'debug'
  195 |     debug("debuginggggggggggggggggggggggggggg");
      |     ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:196:5: note: in expansion of macro 'debug'
  196 |     debug(child);
      |     ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:197:5: note: in expansion of macro 'debug'
  197 |     debug(ord);
      |     ^~~~~
werewolf.cpp: In function 'VI check_validity(int, VI, VI, VI, VI, VI, VI)':
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:260:3: note: in expansion of macro 'debug'
  260 |   debug(l1);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:261:3: note: in expansion of macro 'debug'
  261 |   debug(r1);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:262:3: note: in expansion of macro 'debug'
  262 |   debug(s);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:263:3: note: in expansion of macro 'debug'
  263 |   debug(l);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:271:3: note: in expansion of macro 'debug'
  271 |   debug(l2);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:272:3: note: in expansion of macro 'debug'
  272 |   debug(r2);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:273:3: note: in expansion of macro 'debug'
  273 |   debug(e);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:274:3: note: in expansion of macro 'debug'
  274 |   debug(r);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:330:3: note: in expansion of macro 'debug'
  330 |   debug(perm1);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:331:3: note: in expansion of macro 'debug'
  331 |   debug(perm2);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:344:3: note: in expansion of macro 'debug'
  344 |   debug(qrys);
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:346:3: note: in expansion of macro 'debug'
  346 |   debug("debugging events");
      |   ^~~~~
werewolf.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
werewolf.cpp:348:19: note: in expansion of macro 'debug'
  348 |   trav(x, events) debug(x);
      |                   ^~~~~
werewolf.cpp:31:11: warning: unused variable 'first' [-Wunused-variable]
   31 | #define x first
      |           ^~~~~
werewolf.cpp:48:31: note: in definition of macro 'trav'
   48 | #define trav(a, x) for (auto& a : x)
      |                               ^
werewolf.cpp:348:8: note: in expansion of macro 'x'
  348 |   trav(x, events) debug(x);
      |        ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 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 364 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 10 ms 2540 KB Output is correct
11 Correct 9 ms 2540 KB Output is correct
12 Correct 11 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 12 ms 2796 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1076 ms 148380 KB Output is correct
2 Correct 1263 ms 151864 KB Output is correct
3 Correct 1170 ms 149560 KB Output is correct
4 Correct 1000 ms 148660 KB Output is correct
5 Correct 1002 ms 148640 KB Output is correct
6 Correct 1051 ms 148420 KB Output is correct
7 Correct 1115 ms 148268 KB Output is correct
8 Correct 1373 ms 151848 KB Output is correct
9 Correct 969 ms 149432 KB Output is correct
10 Correct 930 ms 148440 KB Output is correct
11 Correct 922 ms 148404 KB Output is correct
12 Correct 989 ms 148384 KB Output is correct
13 Correct 1341 ms 157220 KB Output is correct
14 Correct 1329 ms 157320 KB Output is correct
15 Correct 1346 ms 157268 KB Output is correct
16 Correct 1354 ms 157320 KB Output is correct
17 Correct 1123 ms 148404 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 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 10 ms 2540 KB Output is correct
11 Correct 9 ms 2540 KB Output is correct
12 Correct 11 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 12 ms 2796 KB Output is correct
16 Correct 1076 ms 148380 KB Output is correct
17 Correct 1263 ms 151864 KB Output is correct
18 Correct 1170 ms 149560 KB Output is correct
19 Correct 1000 ms 148660 KB Output is correct
20 Correct 1002 ms 148640 KB Output is correct
21 Correct 1051 ms 148420 KB Output is correct
22 Correct 1115 ms 148268 KB Output is correct
23 Correct 1373 ms 151848 KB Output is correct
24 Correct 969 ms 149432 KB Output is correct
25 Correct 930 ms 148440 KB Output is correct
26 Correct 922 ms 148404 KB Output is correct
27 Correct 989 ms 148384 KB Output is correct
28 Correct 1341 ms 157220 KB Output is correct
29 Correct 1329 ms 157320 KB Output is correct
30 Correct 1346 ms 157268 KB Output is correct
31 Correct 1354 ms 157320 KB Output is correct
32 Correct 1123 ms 148404 KB Output is correct
33 Correct 1264 ms 148624 KB Output is correct
34 Correct 728 ms 65348 KB Output is correct
35 Correct 1395 ms 151960 KB Output is correct
36 Correct 1159 ms 149380 KB Output is correct
37 Correct 1322 ms 150760 KB Output is correct
38 Correct 1230 ms 149964 KB Output is correct
39 Correct 1211 ms 158932 KB Output is correct
40 Correct 1401 ms 164300 KB Output is correct
41 Correct 1143 ms 150148 KB Output is correct
42 Correct 1008 ms 149176 KB Output is correct
43 Correct 1456 ms 159660 KB Output is correct
44 Correct 1291 ms 150816 KB Output is correct
45 Correct 1142 ms 159596 KB Output is correct
46 Correct 1167 ms 159016 KB Output is correct
47 Correct 1373 ms 157564 KB Output is correct
48 Correct 1283 ms 157236 KB Output is correct
49 Correct 1326 ms 157428 KB Output is correct
50 Correct 1310 ms 157252 KB Output is correct
51 Correct 1374 ms 163880 KB Output is correct
52 Correct 1311 ms 163740 KB Output is correct