제출 #600745

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

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9 + 7;

struct dsu {
    vector<int> p;

    dsu() = default;

    dsu(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int get(int a) {
        return a == p[a] ? a : p[a] = get(p[a]);
    }

    bool mrg(int a, int b) {
        a = get(a);
        b = get(b);
        if (a == b) {
            return false;
        }
        p[b] = a;
        return true;
    }

    bool same(int a, int b) {
        return get(a) == get(b);
    }
};

struct SegTree {
    int sz = 1;
    vector<vector<int>> t;

    SegTree() = default;

    SegTree(const vector<int> &a) {
        int n = (int) a.size();
        sz = 1;
        while (sz < n) sz <<= 1;
        t.assign(sz << 1, {});
        for (int i = 0; i < n; ++i) {
            t[i + sz] = {a[i]};
        }
        for (int i = sz - 1; i > 0; --i) {
            t[i].resize(t[i << 1].size() + t[i << 1 | 1].size());
            merge(t[i << 1].begin(), t[i << 1].end(), t[i << 1 | 1].begin(), t[i << 1 | 1].end(), t[i].begin());
        }
    }

    int get(int l, int r, int val, int x, int lx, int rx) {
        if (l >= rx || lx >= r) return inf;
        if (l <= lx && rx <= r) {
            auto it = lower_bound(t[x].begin(), t[x].end(), val);
            if (it == t[x].end()) {
                return inf;
            } else {
                return *it;
            }
        }
        int m = (lx + rx) >> 1;
        return min(get(l, r, val, x << 1, lx, m), get(l, r, val, x << 1 | 1, m, rx));
    }
};

namespace Werewolf {
    const int N = 600000, logn = 20;
    int jump[logn][N], weight[N], tin[N], tout[N], T = 0;
    vector<int> g[N], ord;

    int n, m;

    void init(vector<array<int, 3>> e, int _n) {
        n = _n;
        m = (int)e.size();
        dsu d(n + m);
        int last = n;
        assert(*max_element(tin, tin + N) == 0);
        for (auto [w, a, b] : e) {
            if (d.same(a, b)) {
                g[last].push_back(d.get(a));
                d.mrg(last, a);
            } else {
                g[last].push_back(d.get(a));
                g[last].push_back(d.get(b));
                d.mrg(last, a);
                d.mrg(last, b);
            }
            weight[last - n] = w;
            last += 1;
        }
        function<void(int)> dfs = [&](int v) {
            tin[v] = T;
            if (v < n) {
                ord.push_back(v);
                T++;
            }
            for (int to : g[v]) {
                jump[0][to] = v;
                dfs(to);
            }
            tout[v] = T;
        };
        memset(tin, -1, sizeof(tin));
        for (int i = last - 1; i > -1; --i) {
            if (tin[i] == -1) {
                jump[0][i] = i;
                dfs(i);
            }
        }
        for (int j = 1; j < logn; ++j) {
            for (int i = 0; i < n + m; ++i) {
                jump[j][i] = jump[j - 1][jump[j - 1][i]];
            }
        }
    }

    pair<int, int> get(int v, int w) {
        for (int j = logn - 1; j > -1; --j) {
            if (weight[jump[j][v] - n] <= w) {
                v = jump[j][v];
            }
        }
        return {tin[v], tout[v]};
    }
};

namespace Human {
    const int N = 600000, logn = 20;
    int jump[logn][N], weight[N], tin[N], tout[N], T = 0;
    vector<int> g[N], ord;

    int n, m;

    void init(vector<array<int, 3>> e, int _n) {
        n = _n;
        m = (int)e.size();
        dsu d(n + m);
        int last = n;
        assert(*max_element(tin, tin + N) == 0);
        for (auto [w, a, b] : e) {
            if (d.same(a, b)) {
                g[last].push_back(d.get(a));
                d.mrg(last, a);
            } else {
                g[last].push_back(d.get(a));
                g[last].push_back(d.get(b));
                d.mrg(last, a);
                d.mrg(last, b);
            }
            weight[last - n] = w;
            last += 1;
        }
        function<void(int)> dfs = [&](int v) {
            tin[v] = T;
            if (v < n) {
                ord.push_back(v);
                T++;
            }
            for (int to : g[v]) {
                jump[0][to] = v;
                dfs(to);
            }
            tout[v] = T;
        };
        memset(tin, -1, sizeof(tin));
        for (int i = last - 1; i > -1; --i) {
            if (tin[i] == -1) {
                jump[0][i] = i;
                dfs(i);
            }
        }
        for (int j = 1; j < logn; ++j) {
            for (int i = 0; i < n + m; ++i) {
                jump[j][i] = jump[j - 1][jump[j - 1][i]];
            }
        }
    }

    pair<int, int> get(int v, int w) {
        for (int j = logn - 1; j > -1; --j) {
            if (weight[jump[j][v] - n] >= w) {
                v = jump[j][v];
            }
        }
        return {tin[v], tout[v]};
    }
} //human


vector<int>
check_validity(int n, vector<int> X, vector<int> Y, vector<int> s, vector<int> e, vector<int> L, vector<int> R) {
    int m = (int)X.size(), q = (int)e.size();
    vector<array<int, 3>> eWerewolf(m), eHuman(m);
    for (int i = 0; i < m; ++i) {
        if (X[i] > Y[i]) {
            swap(X[i], Y[i]);
        }
        eWerewolf[i] = {Y[i], X[i], Y[i]};
        eHuman[i] = {X[i], X[i], Y[i]};
    }
    sort(eHuman.begin(), eHuman.end(), greater());
    sort(eWerewolf.begin(), eWerewolf.end());
    Werewolf::init(eWerewolf, n);
    Human::init(eHuman, n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        a[i] = Human::tin[Werewolf::ord[i]];
    }
    SegTree st(a);
    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        auto [hL, hR] = Human::get(s[i], L[i]);
        auto [wL, wR] = Werewolf::get(e[i], R[i]);
        int x = st.get(wL, wR, hL, 1, 0, st.sz);
        ans[i] = (x < hR);
    }
    return ans;
}

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