Submission #1261431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261431		enxiayy	Werewolf (IOI18_werewolf)	C++20	100 / 100	396 ms	206096 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

#define REP(i, l, r) for(int i = (l); i < (r); ++i)
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, r, l) for(int i = (r); i >= (l); --i)
#define ff first
#define ss second
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;

template<class T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; } 
template<class T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; } 

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }

const int N = 1e6 + 5;

int n, m, q;
vi adj[N], g[N], ask[N], S, E, L, R;
int par[N], tin[N], tout[N], num_nodes = 0, timer = 0;

int acs(int u) { return par[u] == u ? u : par[u] = acs(par[u]); }
bool join(int u, int v) {
    int x = acs(u);
    int y = acs(v);
    if (x == y) return false;
    g[num_nodes].eb(x);
    g[num_nodes].eb(y);
    par[x] = par[y] = par[num_nodes] = num_nodes;
    ++num_nodes;
    return true;
}

void dfs(int u) {
    tin[u] = ++timer;
    for(int v : g[u]) {
        dfs(v);
    }
    tout[u] = timer;
}

int tmp[N];
pair<pii, pii> bound[N];

struct point {
    ll x, y;

    point(ll x = 0, ll y = 0) : x(x), y(y) {}

    bool operator < (const point& o) const {
        return x < o.x;
    }
};

point P[N];
pair<point, point> rect[N];

void reset() {
    num_nodes = n;
    timer = 0;
    REP(i, 0, n + m) {
        g[i].clear();
        par[i] = -1;
        tin[i] = 0;
        tout[i] = 0; 
        tmp[i] = 0;
    }
}

struct query {
    int y, id, type;

    query(int y = 0, int id = 0, int type = 0) : y(y), id(id), type(type) {}
};
vector<query> eq[N];
ll sum[N];

void reset_dsu(int siz) {
    REP(i, 0, siz)
        par[i] = i;
}

void process1() {
    reset();
    reset_dsu(n);
    REP(i, 0, q) {
        ask[L[i]].eb(i);
    }

    FORD(u, n - 1, 0) {
        for(int v : adj[u]) {
            if (v >= u) {
                // cerr << u << " " << v << el;
                join(u, v);
            }
                
        }

        for(int id : ask[u]) {
            tmp[id] = acs(S[id]);
        }
    }

    dfs(num_nodes - 1);

    REP(i, 0, n) {
        P[i].x = tin[i];    
    }

    REP(i, 0, q) {
        // rect[i].first.x = point(tin[tmp[i]], tout[tmp[i]]);
        rect[i].ff.x = tin[tmp[i]];
        rect[i].ss.x = tout[tmp[i]];
    }

    REP(i, 0, q) {
        ask[L[i]].clear();
    }
}

void process2() {
    reset();
    reset_dsu(n);
    REP(i, 0, q) {
        ask[R[i]].eb(i);
    }

    REP(u, 0, n) {
        for(int v : adj[u]) {
            if (v <= u) 
                join(u, v);
        }

        for(int id : ask[u]) {
            tmp[id] = acs(E[id]);
        }
    }

    dfs(num_nodes - 1);

    REP(i, 0, n) {
        P[i].y = tin[i];    
    }

    REP(i, 0, q) {
        // rect[i].first.x = point(tin[tmp[i]], tout[tmp[i]]);
        rect[i].ff.y = tin[tmp[i]];
        rect[i].ss.y = tout[tmp[i]];
    }

    REP(i, 0, q)
        ask[R[i]].clear();
}

struct BIT {
    vector<ll> bit;

    BIT(int n) : bit(n + 5, 0) {}

    void update(int pos) {
        while(pos < sz(bit)) {
            bit[pos] += 1;
            pos += pos & -pos;
        }
    }

    ll get(int pos) {
        ll res = 0;
        while(pos) {
            res += bit[pos];
            pos -= pos & -pos;
        }
        return res;
    }
};

vi check_validity(int N, vi X, vi Y, vi _S, vi _E, vi _L, vi _R) {
    n = N;
    m = sz(X);
    q = sz(_S);

    vi ans;
    ans.resize(q);

    REP(i, 0, m) {
        int u = X[i];
        int v = Y[i];
        adj[u].eb(v);
        adj[v].eb(u);
    }
    S.resize(q), E.resize(q), L.resize(q), R.resize(q);
    REP(i, 0, q) {
        S[i] = _S[i];
        E[i] = _E[i];
        L[i] = _L[i];
        R[i] = _R[i];
    }

    process1();
    process2();

    REP(i, 0, q) {
        int x1, y1, x2, y2;
        x1 = rect[i].ff.x;
        y1 = rect[i].ff.y;
        x2 = rect[i].ss.x;
        y2 = rect[i].ss.y;
        eq[x2].eb(query(y2, i, 1));
        eq[x1 - 1].eb(query(y2, i, -1));
        eq[x2].eb(query(y1 - 1, i, -1));
        eq[x1 - 1].eb(query(y1 - 1, i, 1));
    }

    sort(P, P + n);

    BIT ft(4 * n);
    REP(i, 0, n) {
        ft.update(P[i].y);

        for(auto s : eq[P[i].x]) {
            sum[s.id] += s.type * ft.get(s.y);
        }
    }

    REP(i, 0, q) {
        if (sum[i]) ans[i] = 1;
        else ans[i] = 0;
    }
    return ans;
}


/*

*/

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