제출 #1197281

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197281		_callmelucian	Werewolf (IOI18_werewolf)	C++17	100 / 100	564 ms	132104 KiB

werewolf

#include <bits/stdc++.h>
#ifndef LOCAL
    #include "werewolf.h"
#endif
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct DSU {
    vector<int> lab;
    DSU (int sz) : lab(sz + 1, -1) {}

    int get (int u) {
        if (lab[u] < 0) return u;
        return lab[u] = get(lab[u]);
    }

    int getSz (int u) { return -lab[get(u)]; }

    bool unite (int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return 0;
        if (-lab[a] < -lab[b]) swap(a, b);
        lab[a] += lab[b], lab[b] = a;
        return 1;
    }
};

struct queryItem {
    int st, en, bound, idx;

    queryItem() : st(0), en(0), bound(0), idx(0) {}
    queryItem (int st, int en, int bound, int idx) :
        st(st), en(en), bound(bound), idx(idx) {}
};

const int mn = 6e5 + 5;
int sz[mn], num[mn], chain[mn], depth[mn], par[mn], weight[mn], top[mn], timeDfs;
vector<int> graphAdj[mn], adj[mn];
vector<queryItem> queries[mn];

// custom comparator for set
struct setComp {
    bool operator() (const int &a, const int &b) const { return num[a] < num[b]; }
};
set<int, setComp> markedNode[mn];

void addEdge (int par, int u) {
    adj[par].push_back(top[u]);
    top[u] = par;
}

int szDfs (int u) {
    sz[u] = 1;
    for (int v : adj[u]) sz[u] += szDfs(v);
    return sz[u];
}

void dfs (int u, int p, int d, bool toP) {
    num[u] = ++timeDfs, par[u] = p, depth[u] = d;
    chain[u] = (toP ? chain[p] : u);
    sort(all(adj[u]), [&] (int a, int b) { return sz[a] > sz[b]; });

    bool heavy = 1;
    for (int v : adj[u])
        dfs(v, u, d + 1, heavy), heavy = 0;
}

int lca (int a, int b) {
    int ap = par[chain[a]], bp = par[chain[b]];
    while (chain[a] != chain[b]) {
        if (depth[ap] == depth[bp]) {
            a = ap, ap = par[chain[a]];
            b = bp, bp = par[chain[b]];
        }
        else if (depth[ap] > depth[bp]) a = ap, ap = par[chain[a]];
        else if (depth[bp] > depth[ap]) b = bp, bp = par[chain[b]];
    }
    return (depth[a] < depth[b] ? a : b);
}

vector<int> check_validity (int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    /// process input and prepare offline queries
//    int M = sizeof(X) / sizeof(X[0]), Q = sizeof(S) / sizeof(S[0]);
    int M = X.size(), Q = S.size();
    for (int i = 0; i < M; i++) {
        graphAdj[X[i]].push_back(Y[i]);
        graphAdj[Y[i]].push_back(X[i]);
    }
    for (int i = 0; i < Q; i++)
        queries[L[i]].emplace_back(S[i], E[i], R[i], i);

    /// build DSU tree for MST (with Kruskal)
    int node = N - 1; DSU dsu(N);
    for (int i = 0; i < N; i++) top[i] = weight[i] = i;
    for (int i = 0; i < N; i++) {
        bool firstMerge = 1;
        for (int j : graphAdj[i]) {
            int u = dsu.get(i), v = dsu.get(j);
            if (j > i || !dsu.unite(i, j)) continue;
            if (firstMerge)
                firstMerge = 0, addEdge(++node, u);
            addEdge(node, v);
        }
        if (!firstMerge) weight[node] = i;
    }

    /// process DSU tree
    szDfs(node), dfs(node, node + 1, 1, 0);

    /// build MST (max) and process queries
    vector<int> res(Q);
    dsu = DSU(N);
    for (int i = 0; i < N; i++) markedNode[i].insert(i);
    for (int i = N - 1; i >= 0; i--) {
        for (int j : graphAdj[i]) {
            int u = dsu.get(i), v = dsu.get(j);
            if (j > i && dsu.unite(i, j)) {
                if (u == dsu.get(i)) swap(u, v);
                for (int iter : markedNode[u])
                    markedNode[v].insert(iter);
                markedNode[u].clear();
            }
        }
        for (queryItem &iter : queries[i]) {
            int root = dsu.get(iter.st), opt = INT_MAX;
            auto it = markedNode[root].lower_bound(iter.en);
            if (it != markedNode[root].end()) {
                int lc = lca(iter.en, *it);
                opt = min(opt, weight[lc]);
            }
            if (it != markedNode[root].begin()) {
                int lc = lca(iter.en, *prev(it));
                opt = min(opt, weight[lc]);
            }
            res[iter.idx] = (opt <= iter.bound);
        }
    }
    return res;
}

#ifdef LOCAL
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    vector<int> X = {5, 1, 1, 3, 3, 5};
    vector<int> Y = {1, 2, 3, 4, 0, 2};
    vector<int> S = {4, 4, 5};
    vector<int> E = {2, 2, 4};
    vector<int> L = {1, 2, 3};
    vector<int> R = {2, 2, 4};

    vector<int> res = check_validity(6, X, Y, S, E, L, R);
    for (int u : res) cout << u << " ";

    return 0;
}
#endif

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