제출 #1295995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1295995		baodat	늑대인간 (IOI18_werewolf)	C++20	100 / 100	527 ms	151180 KiB

werewolf

// problem1.cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define FORD(i, l, r) for(int i = l; i >= r; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sp(x) setprecision(x) << fixed
#define db double
#define ldb long double
#define ff first
#define ss second
#define pb push_back
#define ins insert
typedef vector<int> vi;
struct DSU{
    int n;
    vector<int> par, sz;
    DSU(int __n = 0){
        init(__n);
    }
    void init(int __n){
        n = __n;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 1);
        iota(all(par), 0);
    }
    int find_u(int u){
        return u == par[u] ? u : par[u] = find_u(par[u]);
    }
    bool unite(int u, int v){
        u = find_u(u);
        v = find_u(v);
        if(u == v) return false;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
        return true;
    }
};
struct BIT{
  int n;
  vector<int> bit;
  BIT(int __n = 0){
    init(__n);
  }
  void init(int __n){
    n = __n;
    bit.assign(n + 1, 0);
  }
  void update(int i, int v){
    while(i <= n){
      bit[i] += v;
      i += i &-i;
    }
  }
  int query(int i){
    int s = 0;
    while(i > 0){
      s += bit[i];
      i -= i &-i;
    }
    return s;
  }
  int query(int l, int r){
    return query(r) - query(l - 1);
  }
};

const int N = 2e5 + 5;
const int LOG = 20;
int lca_human[2 * N][LOG], lca_wolf[2 * N][LOG];
int tin_human[2 * N], tout_human[2 * N], tin_wolf[2 * N], tout_wolf[2 * N];
int n, m, q, krt_human_w[2 * N], krt_wolf_w[2 * N], pos_human[2 * N], pos_wolf[2 * N];
vi x, y, s, e, l, r;
vi krt_human[2 * N], krt_wolf[2 * N], adj[N];
int timer = 0;
int lift_human(int u, int L){
  if(krt_human_w[u] < L) return -1;
  FORD(j, LOG - 1, 0){
    int p = lca_human[u][j];
    if(p != -1 && krt_human_w[p] >= L) u = p;
  }
  return u;
}

int lift_wolf(int u, int R){
  if(krt_wolf_w[u] > R) return -1;
  FORD(j, LOG - 1, 0){
    int p = lca_wolf[u][j];
    if(p != -1 && krt_wolf_w[p] <= R) u = p;
  }
  return u;
}
void dfs_human(int u){
  tin_human[u] = 1e9;
  tout_human[u] = 0;
  if(u < n){
    pos_human[u] = ++timer;
    tin_human[u] = tout_human[u] = pos_human[u];
  }
  for(int v : krt_human[u]){
    lca_human[v][0] = u;
    FOR(j, 1, LOG - 1){
      if(lca_human[v][j - 1] != -1)
        lca_human[v][j] = lca_human[lca_human[v][j - 1]][j - 1];
    }
    dfs_human(v);
    tin_human[u] = min(tin_human[u], tin_human[v]);
    tout_human[u] = max(tout_human[u], tout_human[v]);
  }
}

void dfs_wolf(int u){
  tin_wolf[u] = 1e9;
  tout_wolf[u] = 0;
  if(u < n){
    pos_wolf[u] = ++timer;
    tin_wolf[u] = tout_wolf[u] = pos_wolf[u];
  }
  for(int v : krt_wolf[u]){
    lca_wolf[v][0] = u;
    FOR(j, 1, LOG - 1){
      if(lca_wolf[v][j - 1] != -1)
        lca_wolf[v][j] = lca_wolf[lca_wolf[v][j - 1]][j - 1];
    }
    dfs_wolf(v);
    tin_wolf[u] = min(tin_wolf[u], tin_wolf[v]);
    tout_wolf[u] = max(tout_wolf[u], tout_wolf[v]);
  }
}

void build_human_tree(){
    int sz = 2 * n;
    DSU dsu(n);
    vi val(n);
    int id = n + 1;
    vector<bool> visited(n, false);
    FOR(i, 0, n - 1) krt_human_w[i] = i;
    iota(all(val), 0);
    FORD(i, n - 1, 0){
        visited[i] = true;
        for(int v : adj[i]){
            if(!visited[v]) continue;
            int r_i = dsu.find_u(i);
            int r_v = dsu.find_u(v);
            if(r_i == r_v) continue;
            int x = id++;
            int node_u = val[r_i], node_v = val[r_v];
            krt_human[x].pb(node_u);
            krt_human[x].pb(node_v);
            krt_human_w[x] = i;
            dsu.unite(r_i, r_v);
            val[dsu.find_u(r_i)] = x;
        }
    }
    timer = 0;
    FORD(i, 2 * n - 1, 0){
        if(lca_human[i][0] == -1){
          dfs_human(i);
        }
    }
}
void build_wolf_tree(){
    int sz = 2 * n;
    DSU dsu(n);
    vi val(n);
    int id = n + 1;
    vector<bool> visited(n, false);
    iota(all(val), 0);
    FOR(i, 0, n - 1) krt_wolf_w[i] = i;
    FOR(i, 0, n - 1){
        visited[i] = true;
        for(int v : adj[i]){
            if(!visited[v]) continue;
            int r_i = dsu.find_u(i);
            int r_v = dsu.find_u(v);
            if(r_i == r_v) continue;
            int x = id++;
            int node_u = val[r_i], node_v = val[r_v];
            krt_wolf[x].pb(node_u);
            krt_wolf[x].pb(node_v);
            krt_wolf_w[x] = i;
            dsu.unite(r_i, r_v);
            val[dsu.find_u(r_i)] = x;
        }
    }
    timer = 0;
    FORD(i, 2 * n - 1, 0){
        if(lca_wolf[i][0] == -1){
          dfs_wolf(i);
        }
    }
}
struct event{
  int x, yl, yr, id, type;
};
vi check_validity(int __n, vi __x, vi __y, vi __s, vi __e, vi __l, vi __r){
    n = __n;
    x = __x;
    y = __y;
    s = __s;
    e = __e;
    l = __l;
    r = __r;
    FOR(i, 0, n - 1) adj[i].clear();
    FOR(i, 0, 2 * n - 1){
        krt_human[i].clear();
        krt_wolf[i].clear();
    }
    timer = 0;
    memset(lca_wolf, -1, sizeof lca_wolf);
    memset(lca_human, -1, sizeof lca_human);
    m = x.size();
    q = s.size();
    FOR(i, 0, m - 1){
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);
    }
    build_wolf_tree();
    build_human_tree();
    //cerr << "can't build";
    vector<pair<int, int>> points(n);
    FOR(i, 0, n - 1){
      points[i] = {pos_human[i], pos_wolf[i]}; //x y
      //x -> human
    }
    //cerr << "hi";
    sort(all(points));
    vector<event> ev;
    vector<int>ans(q, 0);
    FOR(i, 0, q - 1){
      int par_human = lift_human(s[i], l[i]);
      int par_wolf = lift_wolf(e[i], r[i]);
      if(par_human == -1 || par_wolf == -1) continue;
      //ox la then human, oy la theo wolf
      ev.pb({tout_human[par_human], tin_wolf[par_wolf], tout_wolf[par_wolf], i, 1});
      ev.pb({tin_human[par_human] - 1, tin_wolf[par_wolf], tout_wolf[par_wolf], i, -1});
    }
    sort(all(ev), [&](event a, event b){
      return a.x < b.x;
    });
   // cerr << "Step1";
    BIT bit(n + 1);
    int it = 0;
    for(event e : ev){
      while(it < n && points[it].first <= e.x){
        bit.update(points[it].second, 1);
        ++it;
      }
      ans[e.id] += (bit.query(e.yl, e.yr) * e.type);
    }
    FOR(i, 0, q - 1) ans[i] = (ans[i] > 0 ? 1 : 0);
    return ans;
}
void solve(){
    int n = 6, m = 6, q = 3;
    vi x = {5, 1, 1, 3, 3, 5};
    vi y = {1, 2, 3, 4, 0, 2};
    vi s = {4, 4, 5};
    vi e = {2, 2, 4};
    vi l = {1, 2, 3};
    vi r = {2, 2, 4};
    vi ans = check_validity(n, x, y, s, e, l, r);
    for(int i : ans) cout << i << " ";
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51