Submission #290887

#	Time	Username	Problem	Language	Result	Execution time	Memory
290887		ToMmyDong	Werewolf (IOI18_werewolf)	C++11	100 / 100	1576 ms	64752 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define SZ(i) int(i.size())
#define ALL(i) i.begin(), i.end()
#define MEM(i,a) memset(i, (a), sizeof(i))
#define X first
#define Y second
#define eb emplace_back
#define pb push_back
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do (T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<", ";_do(y...);}
template<typename IT> ostream& __printRng (ostream &os, IT bg, IT ed) {
    for (IT it=bg; it!=ed; it++) {
        if (it!=bg) os << "," << *it;
        else os << "{" << *it;
    }
    return os << "}";
}
template<typename T> ostream &operator << (ostream &os, const pair<T,T> &v) {
    return os << "{" << v.X << "," <<v.Y << "}";
}
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) {
    return __printRng(os, ALL(v));
}
template<typename T> ostream &operator << (ostream &os, const set<T> &v) {
    return __printRng(os, ALL(v));
}
#define IOS()
#else
#define debug(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif

struct Djsrng {
    vector<int> djs, sz, l, r, vis;
    int N;
    Djsrng (int n, vector<int> id) : djs(n), sz(n,1), l(n), r(n), vis(n, 0) {
        N = n;
        iota(ALL(djs), 0);
        for (int i=0; i<n; i++) {
            l[i] = r[i] = id[i];
        }
    }

    int fnd (int x) {
        return x == djs[x] ? x : djs[x] = fnd(djs[x]);
    }

    void mrg (int x, int y) {
        x = fnd(x), y = fnd(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        djs[x] = y;
        sz[y] += sz[x];
        l[y] = min(l[y], l[x]);
        r[y] = max(r[x], r[y]);
    }
};

struct Djsid {
    vector<vector<int> > tree;
    vector<int> djs, sz, id, vis;
    int ncnt, N;
    Djsid (int n) : tree(n*2), djs(n), sz(n,1), id(n), vis(n, 0) {
        N = n;
        iota(ALL(djs), 0);
        iota(ALL(id), 0);
        ncnt = n;
    }

    int fnd (int x) {
        return x == djs[x] ? x : djs[x] = fnd(djs[x]);
    }

    void mrg (int x, int y) {
        x = fnd(x), y = fnd(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        djs[x] = y;
        sz[y] += sz[x];
        tree[ncnt].eb(id[x]);
        tree[ncnt].eb(id[y]);
        id[y] = ncnt++;
    }

    void dfs (int nd, vector<int> &res, int &id) {
        if (tree[nd].empty()) res[nd] = id++;
        for (int v : tree[nd]) {
            dfs(v, res, id);
        }
    }

    vector<int> build () {
        vector<int> res(N);
        int id=0;
        dfs(ncnt-1, res, id);
        assert(ncnt == N*2-1);
        return res;
    }
};

vector<int> genId (int n, const vector<vector<int> > &edge, bool rev) {
    vector<int> ord(n);
    iota(ALL(ord), 0);
    if (rev) reverse(ALL(ord));

    Djsid djs(n);
    for (int u : ord) {
        djs.vis[u] = true;
        for (int v : edge[u]) {
            if (djs.vis[v]) {
                djs.mrg(u, v);
            }
        }
    }
    return djs.build();
}

vector<pii> genRng (int n, const vector<vector<int> > &edge, const vector<int> &id, int rev, vector<int> x, vector<int> lim) {
    int q = SZ(x);
    vector<pii> res(q);
    vector<int> ord(n);
    iota(ALL(ord), 0);
    if (rev) reverse(ALL(ord));

    vector<vector<int> > qry(n);
    for (int i=0; i<q; i++) {
        qry[lim[i]].eb(i);
    }
    Djsrng djs(n, id);
    for (int u : ord) {
        djs.vis[u] = true;
        for (int v : edge[u]) {
            if (djs.vis[v]) {
                djs.mrg(u, v);
            }
        }
        for (int qid : qry[u]) {
            res[qid] = {djs.l[djs.fnd(x[qid])],
                        djs.r[djs.fnd(x[qid])]};
        }
    }
    return res;
}

struct bit_2d {
    vector<vector<int> > bit;
    int N;

    bit_2d (int n): bit(n+3) {
        N = n + 3;
    }

    void add (int x, int y) {
        for (x++; x<N; x+=-x&x) {
            bit[x].eb(y);
        }
    }

    void build () {
        for (auto &v : bit) {
            sort(ALL(v));
        }
    }

    int qry (int x, int yl, int yr) {
        int res = 0;
        for (x++; x; x-=-x&x) {
            res += upper_bound(ALL(bit[x]), yr) - 
                   lower_bound(ALL(bit[x]), yl);
        }
        return res;
    }

    int qry (int xl, int xr, int yl, int yr) {
        return qry(xr, yl, yr) - qry(xl-1, yl, yr);
    }
};

vector<int> check_validity(int n, vector<int> x, vector<int> y,
                                vector<int> s, vector<int> e,
                                vector<int> l, vector<int> r) {
    vector<vector<int> > edge(n, vector<int>());
    for (int i=0; i<SZ(x); i++) {
        edge[x[i]].eb(y[i]);
        edge[y[i]].eb(x[i]);
    }
    vector<int> fid = genId(n, edge, 0);
    vector<int> sid = genId(n, edge, 1);
    debug(fid, sid);

    vector<pii> frng = genRng(n, edge, fid, 0, e, r);
    vector<pii> srng = genRng(n, edge, sid, 1, s, l);
    debug(frng, srng);

    bit_2d dt(n);
    for (int i=0; i<n; i++) {
        dt.add(fid[i], sid[i]);
    }
    dt.build();

    vector<int> ans;
    for (int i=0; i<SZ(frng); i++) {
        int res = dt.qry(frng[i].X, frng[i].Y, srng[i].X, srng[i].Y);
        debug(res);
        ans.eb(res > 0);
    }

    return ans;
}

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