oj.uz

Submission #595289

# Submission time Handle Problem Language Result Execution time Memory
595289 2022-07-13T14:31:08 Z Sam_a17 Werewolf (IOI18_werewolf) C++14
100 / 100
 743 ms 108520 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include <cstdio>
using namespace std;

#define pb push_back
#define ld long double
#define ll long long
 
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define lb lower_bound
#define ub upper_bound

const int maxN = 2e5 + 10;
int n, m, q, subX[maxN], subY[maxN], re[maxN];
vector<int> adj[maxN], l[maxN], r[maxN], qq[maxN], answ;

struct dsu {
  int st[maxN], en[maxN], timer;
  vector<int> p, g[maxN];

  void init(int n) {
    p.assign(n + 1, 0);

    for(int i = 0; i < n; i++) {
      p[i] = i;
    }
  }

  int find(int a) {
    if(a != p[a]) {
      p[a] = find(p[a]);
    }
    return p[a];
  }

  void merge(int a, int b) {
    // a -> b
    a = find(a), b = find(b);
    if(a == b) {
      return;
    }

    g[a].push_back(b);
    p[b] = a;
  }

  void get_order(int node) {
    st[node] = timer++;
    for(auto i: g[node]) {
      get_order(i);
    }
    en[node] = timer - 1;
  }

} ri, li;


set<int> st[maxN];

void solve(int node) {
  st[node].insert(ri.st[node]);
  for(auto i: li.g[node]) {
    solve(i);

    // merge
    if(sz(st[i]) > sz(st[node])) {
      st[i].swap(st[node]);
    }

    for(auto j: st[i]) {
      st[node].insert(j);
    }

    st[i].clear();
  }

  for(auto i: qq[node]) {
    int lx = ri.st[re[i]], rx = ri.en[re[i]];
    auto it = st[node].lower_bound(lx);
    if(it != st[node].end() && *it <= rx) {
      answ[i] = 1;
    }
  }
}

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, m = sz(X);

  for(int i = 0; i < m; i++) {
    int a = X[i], b = Y[i];
    adj[a].pb(b);
    adj[b].pb(a);
  }

  q = sz(S), answ.assign(q, 0);

  for(int i = 0; i < q; i++) {
    l[L[i]].push_back(i);
    r[R[i]].push_back(i);
  }

  ri.init(n), li.init(n);

  for(int i = 0; i < n; i++) {
    for(auto j: adj[i]) {
      if(j < i) {
        ri.merge(i, j);
      }
    }

    for(auto j: r[i]) {
      subX[j] = ri.find(E[j]);
      re[j] = subX[j];
    }
  }

  for(int i = n - 1; i >= 0; i--) {
    for(auto j: adj[i]) {
      if(j > i) {
        li.merge(i, j);
      }
    }

    for(auto j: l[i]) {
      subY[j] = li.find(S[j]);
      qq[subY[j]].pb(j);
    }
  }

  li.get_order(li.find(n / 2));
  ri.get_order(ri.find(n / 2));

  solve(li.find(n / 2));
  return answ;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37844 KB Output is correct
2 Correct 20 ms 37844 KB Output is correct
3 Correct 21 ms 37884 KB Output is correct
4 Correct 23 ms 37840 KB Output is correct
5 Correct 21 ms 37948 KB Output is correct
6 Correct 21 ms 37844 KB Output is correct
7 Correct 20 ms 37852 KB Output is correct
8 Correct 29 ms 37852 KB Output is correct
9 Correct 20 ms 37820 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37844 KB Output is correct
2 Correct 20 ms 37844 KB Output is correct
3 Correct 21 ms 37884 KB Output is correct
4 Correct 23 ms 37840 KB Output is correct
5 Correct 21 ms 37948 KB Output is correct
6 Correct 21 ms 37844 KB Output is correct
7 Correct 20 ms 37852 KB Output is correct
8 Correct 29 ms 37852 KB Output is correct
9 Correct 20 ms 37820 KB Output is correct
10 Correct 29 ms 38824 KB Output is correct
11 Correct 22 ms 38740 KB Output is correct
12 Correct 24 ms 38808 KB Output is correct
13 Correct 22 ms 38868 KB Output is correct
14 Correct 24 ms 38860 KB Output is correct
15 Correct 25 ms 38920 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 92172 KB Output is correct
2 Correct 625 ms 90344 KB Output is correct
3 Correct 626 ms 88572 KB Output is correct
4 Correct 646 ms 88688 KB Output is correct
5 Correct 636 ms 89228 KB Output is correct
6 Correct 664 ms 90900 KB Output is correct
7 Correct 620 ms 89060 KB Output is correct
8 Correct 544 ms 90432 KB Output is correct
9 Correct 551 ms 87276 KB Output is correct
10 Correct 505 ms 86892 KB Output is correct
11 Correct 543 ms 86632 KB Output is correct
12 Correct 565 ms 88632 KB Output is correct
13 Correct 554 ms 108520 KB Output is correct
14 Correct 567 ms 108520 KB Output is correct
15 Correct 575 ms 108496 KB Output is correct
16 Correct 538 ms 108492 KB Output is correct
17 Correct 631 ms 88804 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37844 KB Output is correct
2 Correct 20 ms 37844 KB Output is correct
3 Correct 21 ms 37884 KB Output is correct
4 Correct 23 ms 37840 KB Output is correct
5 Correct 21 ms 37948 KB Output is correct
6 Correct 21 ms 37844 KB Output is correct
7 Correct 20 ms 37852 KB Output is correct
8 Correct 29 ms 37852 KB Output is correct
9 Correct 20 ms 37820 KB Output is correct
10 Correct 29 ms 38824 KB Output is correct
11 Correct 22 ms 38740 KB Output is correct
12 Correct 24 ms 38808 KB Output is correct
13 Correct 22 ms 38868 KB Output is correct
14 Correct 24 ms 38860 KB Output is correct
15 Correct 25 ms 38920 KB Output is correct
16 Correct 743 ms 92172 KB Output is correct
17 Correct 625 ms 90344 KB Output is correct
18 Correct 626 ms 88572 KB Output is correct
19 Correct 646 ms 88688 KB Output is correct
20 Correct 636 ms 89228 KB Output is correct
21 Correct 664 ms 90900 KB Output is correct
22 Correct 620 ms 89060 KB Output is correct
23 Correct 544 ms 90432 KB Output is correct
24 Correct 551 ms 87276 KB Output is correct
25 Correct 505 ms 86892 KB Output is correct
26 Correct 543 ms 86632 KB Output is correct
27 Correct 565 ms 88632 KB Output is correct
28 Correct 554 ms 108520 KB Output is correct
29 Correct 567 ms 108520 KB Output is correct
30 Correct 575 ms 108496 KB Output is correct
31 Correct 538 ms 108492 KB Output is correct
32 Correct 631 ms 88804 KB Output is correct
33 Correct 729 ms 90808 KB Output is correct
34 Correct 247 ms 64036 KB Output is correct
35 Correct 729 ms 96004 KB Output is correct
36 Correct 688 ms 90760 KB Output is correct
37 Correct 664 ms 94704 KB Output is correct
38 Correct 651 ms 91716 KB Output is correct
39 Correct 669 ms 96156 KB Output is correct
40 Correct 680 ms 99832 KB Output is correct
41 Correct 629 ms 92364 KB Output is correct
42 Correct 571 ms 87604 KB Output is correct
43 Correct 706 ms 101412 KB Output is correct
44 Correct 594 ms 93340 KB Output is correct
45 Correct 590 ms 92960 KB Output is correct
46 Correct 674 ms 92996 KB Output is correct
47 Correct 591 ms 108436 KB Output is correct
48 Correct 604 ms 108392 KB Output is correct
49 Correct 557 ms 108412 KB Output is correct
50 Correct 574 ms 108520 KB Output is correct
51 Correct 637 ms 97544 KB Output is correct
52 Correct 601 ms 97512 KB Output is correct