oj.uz

Submission #124052

# Submission time Handle Problem Language Result Execution time Memory
124052 2019-07-02T12:27:55 Z RockyB Werewolf (IOI18_werewolf) C++17
100 / 100
 787 ms 98552 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int MAXN = (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n;
vector <int> X, Y, L, R, S, E;
vector <int> g[MAXN], adj[2][MAXN];

bool was[MAXN];

struct dsu {
  int p[MAXN];
  int get(int i) {
    return p[i] == i ? i : p[i] = get(p[i]);
  }
} d;

struct fenwick {
  int f[MAXN];
  void upd(int p, int x) {
    for (; p < MAXN; p |= p + 1) f[p] += x;
  }
  int get(int p) {
    int sum = 0;
    for (; p >= 0; p = (p & (p + 1)) - 1) sum += f[p];
    return sum;
  }
} f;

vector < pair <int, int> > q[2][MAXN];
vector < array <int, 4> > qu[MAXN]; /// i, f, l, r
int sum[MAXN];
int par[2][MAXN];

int tmr;
int tin[2][MAXN], tout[2][MAXN];
int a[2][MAXN];
void dfs(int v, int id) {
  tin[id][v] = ++tmr;
  a[id][tmr] = v;
  /*
  {
    / *
      TODO:
        Then Delete it (it's just for debug)
    * /
    cerr << v << " -> ";
    for (auto to : adj[id][v]) {
      {
        cerr << to << ' ';
      }
    }
    cerr << nl;
  }
  */
  for (auto to : adj[id][v]) {
    if (!tin[id][to]) {
      dfs(to, id);
    }
  }
  tout[id][v] = tmr;
}

vector<int> check_validity(int N, vector<int> _X, vector<int> _Y, vector<int> _S, 
  vector<int> _E, vector<int> _L, vector<int> _R) {

  n = N;
  X = _X;
  Y = _Y;
  S = _S;
  E = _E;
  L = _L;
  R = _R;
  // copy finished
  // checked 1

  rep(i, 0, sz(X)) {
    g[X[i]].pb(Y[i]);
    g[Y[i]].pb(X[i]);
  }
  // checked 1

  rep(i, 0, sz(S)) {
    q[0][L[i]].pb({S[i], i});
    q[1][R[i]].pb({E[i], i});
  }
  // checked 1
  
  per(i, n - 1, 0) {
    d.p[i] = i;
    for (auto to : g[i]) {
      if (!was[to] || d.get(to) == i) continue;
      adj[0][i].pb(d.get(to));
      d.p[d.get(to)] = i;
    }
    for (auto it : q[0][i]) {
      par[0][it.s] = d.get(it.f);
    }
    was[i] = 1;
  }
  // checked 1

  memset(was, 0, sizeof(was));
  rep(i, 0, n) {
    d.p[i] = i;
    for (auto to : g[i]) {
      if (!was[to] || d.get(to) == i) continue;
      adj[1][i].pb(d.get(to));
      d.p[d.get(to)] = i;
    }
    for (auto it : q[1][i]) {
      par[1][it.s] = d.get(it.f);
    }
    was[i] = 1;
  }
  // checked 1

  dfs(0, 0);
  tmr = 0;
  dfs(n - 1, 1);
  // checked 1

  rep(i, 0, sz(S)) {
    int v1 = par[0][i];
    int l1 = tin[0][v1], r1 = tout[0][v1];
    int v2 = par[1][i];
    int l2 = tin[1][v2], r2 = tout[1][v2];

    if (l1) qu[l1 - 1].pb({i, -1, l2, r2});
    qu[r1].pb({i, 1, l2, r2});
  }
  vector <int> ans(sz(S)), pos(n, 0);
  rep(i, 1, n + 1) pos[a[1][i]] = i;
  rep(i, 1, n + 1) {
    f.upd(pos[a[0][i]], 1);
    for (auto it : qu[i]) {
      ans[it[0]] += it[1] * (f.get(it[3]) - f.get(it[2] - 1));
    }
  }
  rep(i, 0, sz(ans)) {
    assert(ans[i] >= 0);
    if (ans[i] > 0) ans[i] = 1;
    else ans[i] = 0;
  }
  return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28792 KB Output is correct
2 Correct 28 ms 28792 KB Output is correct
3 Correct 28 ms 28796 KB Output is correct
4 Correct 28 ms 28764 KB Output is correct
5 Correct 28 ms 28792 KB Output is correct
6 Correct 29 ms 28792 KB Output is correct
7 Correct 28 ms 28792 KB Output is correct
8 Correct 28 ms 28792 KB Output is correct
9 Correct 28 ms 28792 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28792 KB Output is correct
2 Correct 28 ms 28792 KB Output is correct
3 Correct 28 ms 28796 KB Output is correct
4 Correct 28 ms 28764 KB Output is correct
5 Correct 28 ms 28792 KB Output is correct
6 Correct 29 ms 28792 KB Output is correct
7 Correct 28 ms 28792 KB Output is correct
8 Correct 28 ms 28792 KB Output is correct
9 Correct 28 ms 28792 KB Output is correct
10 Correct 34 ms 29816 KB Output is correct
11 Correct 34 ms 29752 KB Output is correct
12 Correct 34 ms 29688 KB Output is correct
13 Correct 36 ms 30024 KB Output is correct
14 Correct 40 ms 29944 KB Output is correct
15 Correct 35 ms 29844 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 85124 KB Output is correct
2 Correct 639 ms 89464 KB Output is correct
3 Correct 603 ms 85752 KB Output is correct
4 Correct 625 ms 83756 KB Output is correct
5 Correct 630 ms 83672 KB Output is correct
6 Correct 668 ms 85112 KB Output is correct
7 Correct 568 ms 80864 KB Output is correct
8 Correct 581 ms 89336 KB Output is correct
9 Correct 520 ms 83272 KB Output is correct
10 Correct 523 ms 81948 KB Output is correct
11 Correct 553 ms 82136 KB Output is correct
12 Correct 644 ms 82384 KB Output is correct
13 Correct 621 ms 93792 KB Output is correct
14 Correct 614 ms 93784 KB Output is correct
15 Correct 631 ms 93752 KB Output is correct
16 Correct 620 ms 93876 KB Output is correct
17 Correct 568 ms 80720 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28792 KB Output is correct
2 Correct 28 ms 28792 KB Output is correct
3 Correct 28 ms 28796 KB Output is correct
4 Correct 28 ms 28764 KB Output is correct
5 Correct 28 ms 28792 KB Output is correct
6 Correct 29 ms 28792 KB Output is correct
7 Correct 28 ms 28792 KB Output is correct
8 Correct 28 ms 28792 KB Output is correct
9 Correct 28 ms 28792 KB Output is correct
10 Correct 34 ms 29816 KB Output is correct
11 Correct 34 ms 29752 KB Output is correct
12 Correct 34 ms 29688 KB Output is correct
13 Correct 36 ms 30024 KB Output is correct
14 Correct 40 ms 29944 KB Output is correct
15 Correct 35 ms 29844 KB Output is correct
16 Correct 787 ms 85124 KB Output is correct
17 Correct 639 ms 89464 KB Output is correct
18 Correct 603 ms 85752 KB Output is correct
19 Correct 625 ms 83756 KB Output is correct
20 Correct 630 ms 83672 KB Output is correct
21 Correct 668 ms 85112 KB Output is correct
22 Correct 568 ms 80864 KB Output is correct
23 Correct 581 ms 89336 KB Output is correct
24 Correct 520 ms 83272 KB Output is correct
25 Correct 523 ms 81948 KB Output is correct
26 Correct 553 ms 82136 KB Output is correct
27 Correct 644 ms 82384 KB Output is correct
28 Correct 621 ms 93792 KB Output is correct
29 Correct 614 ms 93784 KB Output is correct
30 Correct 631 ms 93752 KB Output is correct
31 Correct 620 ms 93876 KB Output is correct
32 Correct 568 ms 80720 KB Output is correct
33 Correct 692 ms 85508 KB Output is correct
34 Correct 368 ms 69092 KB Output is correct
35 Correct 723 ms 88824 KB Output is correct
36 Correct 712 ms 85496 KB Output is correct
37 Correct 706 ms 87736 KB Output is correct
38 Correct 728 ms 86108 KB Output is correct
39 Correct 680 ms 98552 KB Output is correct
40 Correct 736 ms 90140 KB Output is correct
41 Correct 669 ms 85916 KB Output is correct
42 Correct 559 ms 81760 KB Output is correct
43 Correct 767 ms 93304 KB Output is correct
44 Correct 689 ms 87384 KB Output is correct
45 Correct 634 ms 95808 KB Output is correct
46 Correct 612 ms 96368 KB Output is correct
47 Correct 624 ms 93360 KB Output is correct
48 Correct 711 ms 93140 KB Output is correct
49 Correct 648 ms 93284 KB Output is correct
50 Correct 646 ms 93140 KB Output is correct
51 Correct 663 ms 88940 KB Output is correct
52 Correct 669 ms 88852 KB Output is correct