Submission #1234490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234490		nicolo_010	늑대인간 (IOI18_werewolf)	C++20	100 / 100	828 ms	101892 KiB

werewolf

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll  = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)
template<typename T>
using v = vector<T>;
const int INF = 1e9;

struct DSU {
    v<int> parent;

    DSU(int n) {
        parent.resize(n);
        rep(i, 0, n) parent[i] = i;
    }

    int find(int n) {
        return (parent[n] == n ? n : parent[n] = find(parent[n]));
    }

    void join(int a, int b, v<pii>&tree) {
        a = find(a);
        b = find(b);
        if (a != b) {
            int p = parent.size();
            parent[a] = parent[b] = p;
            parent.push_back(p);
            tree.push_back({a, b});
        }
    }
};

int t = 0;

pair<int, int> dfs(v<pii> &tree, int u, int N) {
    if (u < N) {
        tree[u] = {t, t};
        t++;
    }
    else {
        pii A = dfs(tree, tree[u].first, N);
        pii B = dfs(tree,tree[u].second, N);
        tree[u].first = min(A.first, B.first);
        tree[u].second = max(A.second, B.second);
    }
    return tree[u];
}

v<pii> points;

struct SegTree {
    v<v<int>> tree;
    v<v<int>> pts;
    SegTree(int n) {
        tree.assign(4*n, {});
        pts.resize(n);
        rep(i, 0, n) {
            pts[points[i].first].push_back(points[i].second);
        }
        rep(i, 0, n) {
            sort(pts[i].begin(), pts[i].end());
        }
        build(1, 0, n-1);
    }

    void build(int p, int l, int r) {
        if (l == r) {
            tree[p] = pts[l];
        }
        else {
            build(2*p, l, (l+r)/2);
            build(2*p+1, (l+r)/2+1, r);
            merge(tree[2*p].begin(), tree[2*p].end(),
                tree[2*p+1].begin(), tree[2*p+1].end(),
                back_inserter(tree[p]));
        }
    }

    int query(int p, int l, int r, int xl, int xr, int yl, int yr) {
        if (l > xr || r < xl) return 0;
        if (xl <= l && r <= xr)  {
            auto it = lower_bound(tree[p].begin(), tree[p].end(), yl) - tree[p].begin();
            auto it2 = upper_bound(tree[p].begin(), tree[p].end(), yr) - tree[p].begin();
            return it2 - it;
        }
        else {
            int m = (l+r)/2;
            int i1 = query(2*p, l, m, xl, xr, yl, yr);
            int i2 = query(2*p+1, m+1, r, xl, xr, yl, yr);
            return i1 + i2;
        }
    }

};

v<int> check_validity(int N, v<int> X, v<int> Y, v<int> S, v<int> E, v<int> L, v<int> R) {
    int M = X.size();
    int Q = L.size();
    L.push_back(0);
    R.push_back(N-1);
    S.push_back(0);
    E.push_back(0);
    v<pii> Lorder(Q+1);
    v<pii> Rorder(Q+1);
    rep(i, 0, Q+1) {
        Lorder[i] = {L[i], i};
        Rorder[i] = {R[i], i};
    }
    v<pii> vL(Q);
    v<pii> vR(Q);


    //vL recognition
    sort(Lorder.begin(), Lorder.end(), greater<>());
    DSU dsuL(N);
    v<pair<int, pii>> edgesL(M);
    rep(i, 0, M) {
        edgesL[i] = {min(X[i], Y[i]), {X[i], Y[i]}};
    }
    sort(edgesL.begin(), edgesL.end(), greater<>());
    int j = 0;
    v<int> leadL(Q+1);
    v<pii> treeL(N);
    rep(i, 0, Q+1) {
        while (j < M && edgesL[j].first >= Lorder[i].first) {
            dsuL.join(edgesL[j].second.first, edgesL[j].second.second, treeL);
            //cout << i << " " << edgesL[j].second.first << " " << edgesL[j].second.second << endl;
            j++;
        }
        //cout << i << " " << S[Lorder[i].second] << " " << dsuL.parent[6 ] << " " << dsuL.parent.size() << endl;
        leadL[Lorder[i].second] = dsuL.find(S[Lorder[i].second]);
    }
    t = 0;
    dfs(treeL, treeL.size()-1, N);
    rep(i, 0, Q) {
        vL[i] = treeL[leadL[i]];
    }
    //vR recognition
    sort(Rorder.begin(), Rorder.end());
    DSU dsuR(N);
    v<pair<int, pii>> edgesR(M);
    rep(i, 0, M) {
        edgesR[i] = {max(X[i], Y[i]), {X[i], Y[i]}};
    }
    sort(edgesR.begin(), edgesR.end());
    j = 0;
    v<int> leadR(Q+1);
    v<pii> treeR(N);
    rep(i, 0, Q+1) {
        while (j < M && edgesR[j].first <= Rorder[i].first) {
            dsuR.join(edgesR[j].second.first, edgesR[j].second.second, treeR);
            j++;
        }
        leadR[Rorder[i].second] = dsuR.find(E[Rorder[i].second]);
    }
    t = 0;
    dfs(treeR, treeR.size()-1, N);
    rep(i, 0, Q) {
        vR[i] = treeR[leadR[i]];
    }
    //Query preprocessing

    points.resize(N);
    rep(i, 0, N) {
        points[i] = {treeL[i].first, treeR[i].first};
    }
    sort(points.begin(), points.end());
    SegTree st(N);
    v<int> ans(Q);
    rep(i, 0, Q) {
        int que = st.query(1, 0, N-1, vL[i].first, vL[i].second, vR[i].first, vR[i].second);
        //cout << que << endl;
        ans[i] = que > 0;
    }
    return ans;
}

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