Submission #1190579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190579		Numberz	Werewolf (IOI18_werewolf)	C++20	0 / 100	480 ms	589824 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("popcnt")
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define vll vector<ll>
#define vvll vector<vll>
const ll INF = 1e18;
const int MAXN = 2e5 + 5;

struct DSUTree {
    vector<int> parent;
    vector<pii> children;
    DSUTree(int n): parent(n), children(n, {-1,-1}) {iota(parent.begin(), parent.end(), 0);}
    int find(int x) {return parent[x] < 0 ? x : parent[x] = find(parent[x]);}
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        int p = parent.size();
        parent[x] = parent[y] = p;
        parent.push_back(-1);
        children.emplace_back(y, x);
    }
};

vector<pii> rangeDFS;
int dfsTimer;
void dfsRanges(const vector<pii>& children, int v) {
    if (v < rangeDFS.size()/2 + 1 && children[v].first == -1) {
        rangeDFS[v] = {dfsTimer, dfsTimer};
        dfsTimer++;
    } else if (v >= 0) {
        int l = children[v].first, r = children[v].second;
        dfsRanges(children, l);
        dfsRanges(children, r);
        rangeDFS[v].first = min(rangeDFS[l].first, rangeDFS[r].first);
        rangeDFS[v].second = max(rangeDFS[l].second, rangeDFS[r].second);
    }
}

struct Tree2D {
    int n, base;
    vector<pii> pts;
    vector<vector<int>> tree;
    Tree2D(const vector<pii>& points) {
        pts = points;
        sort(pts.begin(), pts.end());
        n = pts.size(); base = 1;
        while (base < n) base <<= 1;
        tree.assign(2*base, {});
        for (int i = 0; i < n; i++) tree[base + i].push_back(pts[i].second);
        for (int i = base - 1; i >= 1; --i) {
            auto &L = tree[2*i], &R = tree[2*i+1];
            tree[i].resize(L.size() + R.size());
            merge(L.begin(), L.end(), R.begin(), R.end(), tree[i].begin());
        }
    }
    int countInNode(int idx, int yL, int yR) {
        auto &v = tree[idx];
        int lo = lower_bound(v.begin(), v.end(), yL) - v.begin();
        int hi = upper_bound(v.begin(), v.end(), yR) - v.begin();
        return hi - lo;
    }
    int query(int xL, int xR, int yL, int yR) {
        int l = lower_bound(pts.begin(), pts.end(), make_pair(xL, -1)) - pts.begin();
        int r = lower_bound(pts.begin(), pts.end(), make_pair(xR+1, -1)) - pts.begin() - 1;
        if (l > r) return 0;
        int res = 0;
        l += base; r += base;
        while (l <= r) {
            if (l & 1) res += countInNode(l++, yL, yR);
            if (!(r & 1)) res += countInNode(r--, yL, yR);
            l >>= 1; r >>= 1;
        }
        return res;
    }
};


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 N = n, M = X.size(), Q = S.size();
    struct Edge { int u,v,w; };
    vector<Edge> edgesH(M);
    for (int i = 0; i < M; i++) edgesH[i] = {X[i], Y[i], min(X[i], Y[i])};
    sort(edgesH.begin(), edgesH.end(), [](auto &a, auto &b){ return a.w > b.w; });
    vector<int> orderL(Q);
    iota(orderL.begin(), orderL.end(), 0);
    sort(orderL.begin(), orderL.end(), [&](int a, int b){ return L[a] > L[b]; });
    vector<int> leadH(Q);
    DSUTree dsuH(N);
    int ptr = 0;
    for (int idx : orderL) {
        while (ptr < M && edgesH[ptr].w > L[idx]) {
            dsuH.unite(edgesH[ptr].u, edgesH[ptr].v);
            ptr++;
        }
        leadH[idx] = dsuH.find(S[idx]);
    }
    int totalH = dsuH.parent.size();
    vector<pii> childrenH = dsuH.children;
    rangeDFS.assign(totalH, {-1,-1}); dfsTimer = 0;
    dfsRanges(childrenH, totalH - 1);
    vector<pii> rangeH(totalH);
    for (int i = 0; i < totalH; i++) rangeH[i] = rangeDFS[i];
    vector<pii> LR(Q);
    for (int i = 0; i < Q; i++) LR[i] = rangeH[leadH[i]];
    vector<Edge> edgesW(M);
    for (int i = 0; i < M; i++) edgesW[i] = {X[i], Y[i], max(X[i], Y[i])};
    sort(edgesW.begin(), edgesW.end(), [](auto &a, auto &b){ return a.w < b.w; });
    vector<int> orderR(Q);
    iota(orderR.begin(), orderR.end(), 0);
    sort(orderR.begin(), orderR.end(), [&](int a, int b){ return R[a] < R[b]; });
    vector<int> leadW(Q);
    DSUTree dsuW(N);
    ptr = 0;
    for (int idx : orderR) {
        while (ptr < M && edgesW[ptr].w < R[idx]) {
            dsuW.unite(edgesW[ptr].u, edgesW[ptr].v);
            ptr++;
        }
        leadW[idx] = dsuW.find(E[idx]);
    }
    int totalW = dsuW.parent.size();
    vector<pii> childrenW = dsuW.children;
    rangeDFS.assign(totalW, {-1,-1}); dfsTimer = 0;
    dfsRanges(childrenW, totalW - 1);
    vector<pii> rangeW(totalW);
    for (int i = 0; i < totalW; i++) rangeW[i] = rangeDFS[i];
    vector<pii> RR(Q);
    for (int i = 0; i < Q; i++) RR[i] = rangeW[leadW[i]];
    vector<pii> pts(N);
    for (int i = 0; i < N; i++) pts[i] = { rangeH[i].first, rangeW[i].first };
    Tree2D tree2d(pts);
    vector<int> ans(Q);
    for (int i = 0; i < Q; i++) {
        int xl = LR[i].first, xr = RR[i].second;
        int yl = RR[i].first, yr = RR[i].second;
        ans[i] = (tree2d.query(xl, xr, yl, yr) > 0);
    }
    
    return ans;
}

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