oj.uz

Submission #595288

# Submission time Handle Problem Language Result Execution time Memory
595288 2022-07-13T14:30:37 Z Sam_a17 Werewolf (IOI18_werewolf) C++14
0 / 100
 705 ms 91728 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;
  }

} 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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37844 KB Output is correct
2 Incorrect 20 ms 37916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37844 KB Output is correct
2 Incorrect 20 ms 37916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 705 ms 91728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37844 KB Output is correct
2 Incorrect 20 ms 37916 KB Output isn't correct
3 Halted 0 ms 0 KB -