Submission #772272

#	Time	Username	Problem	Language	Result	Execution time	Memory
772272		PixelCat	Werewolf (IOI18_werewolf)	C++14	0 / 100	316 ms	59676 KiB

werewolf

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include "werewolf.h"

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define F first
#define S second
using namespace std;
using pii = pair<int, int>;

const int MAXN = 200000;

struct DSU {
    int p[MAXN + 10];
    int rk[MAXN + 10];
    vector<int> adj[MAXN + 10];
    int l[MAXN + 10], r[MAXN + 10];
    int cur_id;

    void init(int n) {
        cur_id = 0;
        For(i, 0, n - 1) {
            adj[i].clear();
            l[i] = r[i] = i;
            p[i] = -1;
            rk[i] = 1;
        }
    }
    int find(int n) {
        if(p[n] < 0) return n;
        return find(p[n]);
    }
    void uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return;
        if(rk[a] < rk[b]) swap(a, b);
        p[b] = a;
        adj[a].eb(b);
        rk[a] += rk[b];
        r[a] = r[b];
    }
    void dfs(int n, int *id) {
        id[n] = cur_id;
        cur_id++;
        for(auto &i:adj[n]) {
            dfs(i, id);
        }
    }
    void build_tree(int n, int *id) {
        For(i, 0, n - 1) if(p[i] < 0) {
            dfs(i, id);
        }
    }
    void out(int n) {
        cerr << "Tree:\n";
        For(i, 0, n - 1) cerr << p[i] << " \n"[i == n - 1];
        For(i, 0, n - 1) cerr << l[i] << " \n"[i == n - 1];
        For(i, 0, n - 1) cerr << r[i] << " \n"[i == n - 1];
    }
} dsu;

#define LO(x) ((x) & (-(x)))
struct BIT {
    int n;
    int a[MAXN + 10];
    void init(int _n) {
        n = _n;
        memset(a, 0, sizeof(a));
    }
    void add(int i, int x) {
        i++;
        while(i <= n) {
            a[i] += x;
            i += LO(i);
        }
    }
    int ask(int i) {
        i++;
        int res = 0;
        while(i) {
            res += a[i];
            i -= LO(i);
        }
        return res;
    }
    int ask(int l, int r) {
        return ask(r - ask(l - 1));
    }
} bit;

struct Query {
    int s, e, l, r;
    int sl, sr, el, er;
    int ans;
};

struct SwpEvent {
    Query* qry;
    bool add;  // true for +, false for -
    int x;
};

vector<int> adj[MAXN + 10];
int px[MAXN + 10];
int py[MAXN + 10];
Query queries[MAXN + 10];

// stage 1: build trees & find ranges
void owo1(int n, int q) {
    vector<Query*> qrys(q);
    For(i, 0, q - 1) {
        qrys[i] = queries + i;
    }
    int ptr;

    sort(all(qrys), [&](Query* const &p1, Query* const &p2) {
        return p1->l > p2->l;
    });
    ptr = 0;
    dsu.init(n);
    Forr(i, n - 1, 0) {
        for(auto &j:adj[i]) if(j > i) {
            dsu.uni(i, j);
        }
        while(ptr < q && qrys[ptr]->l == i) {
            auto &qry = *qrys[ptr];
            int rt = dsu.find(qry.s);
            qry.sl = dsu.l[rt];
            qry.sr = dsu.r[rt];
            ptr++;
        }
    }
    dsu.build_tree(n, px);
    For(i, 0, q - 1) {
        auto &qry = queries[i];
        qry.sl = px[qry.sl];
        qry.sr = px[qry.sr];
    }
    // dsu.out(n);

    sort(all(qrys), [&](Query* const &p1, Query* const &p2) {
        return p1->r < p2->r;
    });
    ptr = 0;
    dsu.init(n);
    For(i, 0, n - 1) {
        for(auto &j:adj[i]) if(j < i) {
            dsu.uni(i, j);
        }
        while(ptr < q && qrys[ptr]->r == i) {
            auto &qry = *qrys[ptr];
            int rt = dsu.find(qry.e);
            qry.el = dsu.l[rt];
            qry.er = dsu.r[rt];
            ptr++;
        }
    }
    dsu.build_tree(n, py);
    For(i, 0, q - 1) {
        auto &qry = queries[i];
        qry.el = py[qry.el];
        qry.er = py[qry.er];
    }
    // dsu.out(n);

    // For(i, 0, q - 1) {
    //     auto &qry = queries[i];
    //     cerr << qry.sl << "," << qry.sr << "  " << qry.el << "," << qry.er << "\n";
    // }
}

// stage 2: do sweeping line
void owo2(int n, int q) {
    vector<SwpEvent> ev;
    For(i, 0, q - 1) {
        ev.push_back((SwpEvent){ queries + i, 0, queries[i].sl - 1 });
        ev.push_back((SwpEvent){ queries + i, 1, queries[i].sr });
    }
    sort(all(ev), [&](const SwpEvent &a, const SwpEvent &b) {
        return a.x < b.x;
    });
    int ptr = 0;
    while(ptr < sz(ev) && ev[ptr].x < 0) {
        ptr++;
    }

    vector<int> y(n, -1);
    For(i, 0, n - 1) {
        y[px[i]] = py[i];
        // cerr << px[i] << " " << py[i] << "\n";
    }

    bit.init(n);
    For(x, 0, n - 1) {
        bit.add(y[x], 1);
        while(ptr < sz(ev) && ev[ptr].x == x) {
            Query *qry = ev[ptr].qry;
            int res = bit.ask(qry->el, qry->er);
            if(ev[ptr].add) qry->ans += res;
            else qry->ans -= res;
            ptr++;
        }
    }
}

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 Q = sz(S);
    For(i, 0, sz(X) - 1) {
        int a = X[i], b = Y[i];
        adj[a].eb(b);
        adj[b].eb(a);
    }
    For(i, 0, Q - 1) {
        auto &qry = queries[i];
        qry.s = S[i];
        qry.e = E[i];
        qry.l = L[i];
        qry.r = R[i];
    }

    owo1(N, Q);
    owo2(N, Q);

    vector<int> ans;
    For(i, 0, Q - 1) {
        ans.eb(queries[i].ans != 0);
    }
    return ans;
    
    // int Q = S.size();
    // vector<int> A(Q);
    // for (int i = 0; i < Q; ++i) {
    //     A[i] = 0;
    // }
    // return A;
}

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