제출 #568349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
568349		elazarkoren	늑대인간 (IOI18_werewolf)	C++17	100 / 100	2225 ms	202212 KiB

werewolf

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 4e5 + 5;

struct Dsu {
    int n;
    vi loga, par, tim;
    vvi dp, tree;
    vi l, r;
    Dsu() {}
    Dsu(int n): n(n) {
        par.resize(n);
        iota(all(par), 0);
        dp.resize(1, vi(n));
        tree.resize(n);
        tim.resize(n);
    }
    inline void Add(int t) {
        par.push_back(n), dp[0].push_back(n);
        tree.push_back({});
        tim.push_back(t);
        n++;
    }
    int Find(int i) {
        return par[i] == i ? i : par[i] = Find(par[i]);
    }
    void Union(int a, int b, int t) {
        int pa = Find(a), pb = Find(b);
        if (pa == pb) return;
        dp[0][pa] = dp[0][pb] = n;
        par[pa] = par[pb] = n;
        Add(t);
        tree.back().push_back(pa);
        tree.back().push_back(pb);
    }
    void PreOrder(int node, int &t) {
        if (tree[node].empty()) {
            l[node] = t++;
            r[node] = t;
            return;
        }
        l[node] = n, r[node] = 0;
        for (int neighbor : tree[node]) {
            PreOrder(neighbor, t);
            chkmin(l[node], l[neighbor]), chkmax(r[node], r[neighbor]);
        }
    }
    void Build() {
        loga.resize(n + 1);
        for (int i = 2; i <= n; i++) loga[i] = loga[i >> 1] + 1;
        dp.resize(loga[n] + 1, vi(n));
        for (int i = 1; i <= loga[n]; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = dp[i - 1][dp[i - 1][j]];
            }
        }
        int t = 0;
        l.resize(n), r.resize(n);
        PreOrder(n - 1, t);
    }
    int Jump(int node, int t) {
        for (int i = loga[n]; i >= 0; i--) {
            if (tim[dp[i][node]] <= t) {
                node = dp[i][node];
            }
        }
        return node;
    }
};

struct Seg {
    vi seg, lp, rp;
    Seg() {Add();}
    inline void Add() {
        seg.push_back(0), lp.push_back(0), rp.push_back(0);
    }
    int update(int i, int ind, int l = 0, int r = MAX_N) {
        int copy = seg.size();
        Add();
        seg[copy] = seg[ind];
        lp[copy] = lp[ind], rp[copy] = rp[ind];
        if (l + 1 == r) {
            seg[copy] = 1;
            return copy;
        }
        if (i < (l + r) >> 1) {
            if (!lp[ind]) {
                lp[ind] = seg.size();
                Add();
            }
            int y = update(i, lp[ind], l, (l + r) >> 1);
            lp[copy] = y;
        } else {
            if (!rp[ind]) {
                rp[ind] = seg.size();
                Add();
            }
            int y = update(i, rp[ind],(l + r) >> 1, r);
            rp[copy] = y;
        }
        seg[copy]++;
        return copy;
    }
    int query(int a, int b, int ind, int l = 0, int r = MAX_N) {
        if (a <= l && r <= b) return seg[ind];
        if (r <= a || b <= l) return 0;
        return (lp[ind] ? query(a, b, lp[ind], l, (l + r) >> 1) : 0) +
               (rp[ind] ? query(a, b, rp[ind], (l + r) >> 1, r) : 0);
    }
};

Seg seg = Seg();

int n;
int ind[MAX_N];
int roots[MAX_N];

inline int Sum(int x1, int y1, int x2, int y2) {
    int v1 = seg.query(y1, y2, roots[x2]), v2 = seg.query(y1, y2, roots[x1]);
    return v1 - v2;
}

vi check_validity(int N, vi X, vi Y, vi s, vi e, vi l, vi r) {
    n = N;
    int m = X.size();
    iota(ind, ind + m, 0);
    Dsu d_min(n), d_max(n);
    sort(ind, ind + m, [&] (int i, int j) {
        return max(X[i], Y[i]) < max(X[j], Y[j]);
    });
    for (int i = 0; i < m; i++) {
        d_min.Union(X[ind[i]], Y[ind[i]], max(X[ind[i]], Y[ind[i]]));
    }
    sort(ind, ind + m, [&] (int i, int j) {
        return min(X[i], Y[i]) > min(X[j], Y[j]);
    });
    for (int i = 0; i < m; i++) {
        d_max.Union(X[ind[i]], Y[ind[i]], n - min(X[ind[i]], Y[ind[i]]));
    }
    d_min.Build(), d_max.Build();
    vii points(n);
    for (int i = 0; i < n; i++) {
        points[i] = {d_min.l[i], d_max.l[i]};
    }
    sort(all(points));
    for (int i = 0; i < n; i++) {
        roots[i + 1] = seg.update(points[i].y, roots[i]);
    }
    int q = s.size();
    vi ans(q);
    for (int i = 0; i < q; i++) {
        int t_min = r[i], t_max = n - l[i];
        int v1 = d_min.Jump(e[i], t_min), v2 = d_max.Jump(s[i], t_max);
        int x1 = d_min.l[v1], x2 = d_min.r[v1], y1 = d_max.l[v2], y2 = d_max.r[v2];
        ans[i] = Sum(x1, y1, x2, y2) != 0;
    }
    return ans;
}
//6 6 3
//5 1
//1 2
//1 3
//3 4
//3 0
//5 2
//4 2 1 2
//4 2 2 2
//5 4 3 4

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