Submission #241977

#	Time	Username	Problem	Language	Result	Execution time	Memory
241977		abacaba	Werewolf (IOI18_werewolf)	C++14	100 / 100	1250 ms	152680 KiB

werewolf

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
 
inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}
 
inline void setout(string s) {
    freopen(s.c_str(), "w", stdout);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}
 
const int inf = 2e9;
const int mod = 998244353;
const int N = 2e5 + 15;
const int L = 19;
const int M = 4e5 + 15;
int n, q;
vector <int> g[N];

int l[M], r[M];

int k[M], tin[M], tout[M], tt, up[L][M];

int backtin[N];

struct dsu {
    int p[N], sz[N];
    dsu() {
        for(int i = 0; i < N; ++i)
            p[i] = i, sz[i] = 1;
    }
    int find(int v) {
        if(v == p[v])
            return v;
        return p[v] = find(p[v]);
    }
    void unio(int a, int b) {
        a = find(a);
        b = find(b);
        if(a != b) {
            if(sz[a] < sz[b])
                swap(a, b);
            p[b] = a;
            sz[a] += sz[b];
        }
    }
} rt;

set <int> is[N];

struct dsu_with_set {
    int p[N];
    dsu_with_set() {
        for(int i = 0; i < N; ++i)
            p[i] = i;
    }
    int find(int v) {
        if(v == p[v])
            return v;
        return p[v] = find(p[v]);
    }
    void unio(int a, int b) {
        a = find(a);
        b = find(b);
        if(a != b) {
            if(is[a].size() < is[b].size())
                swap(a, b);
            p[b] = a;
            is[a].insert(is[b].begin(), is[b].end());
        }
    }
} s;

struct query {
    int l, r, s, e, ind;
    bool operator < (const query &rhs) const {
        return r < rhs.r;
    }
} qs[N];

vector <pii> e;

int cur[N];

inline int getk(int v, int val) {
    for(int i = L - 1; i >= 0; --i)
        if(k[up[i][v]] >= val)
            v = up[i][v];
    return v;
}

void build(int v, int p) {
    up[0][v] = p;
    for(int i = 1; i < L; ++i)
        up[i][v] = up[i-1][up[i-1][v]];
    if(v < n) {
        tin[v] = tout[v] = tt++;
    }
    else {
        build(l[v], v);
        build(r[v], v);
        tin[v] = tin[l[v]];
        tout[v] = tout[r[v]];
    }
}

inline void build_reachability_tree() {
    sort(e.begin(), e.end(), [&](pii a, pii b) {
        return min(a.f, a.se) > min(b.f, b.se);
    });
    int nw = n;
    for(int i = 0; i < n; ++i)
        cur[i] = k[i] = i;
    for(int i = 0; i < e.size(); ++i) {
        int u = e[i].f, v = e[i].se;
        if(rt.find(u) != rt.find(v)) {
            l[nw] = cur[rt.find(u)];
            r[nw] = cur[rt.find(v)];
            rt.unio(u, v);
            k[nw] = min(u, v);
            cur[rt.find(u)] = nw++;
        }
    }
    build(nw - 1, nw - 1);
    for(int i = 0; i < n; ++i)
        backtin[tin[i]] = i;
    for(int i = 0; i < n; ++i)
        is[i].insert(tin[i]);
}

inline void add(int v) {
    for(int to : g[v])
        if(to < v)
            s.unio(to, v);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
    n = N, q = S.size();
    vector<int> ans(q, 0);
    for(int i = 0; i < X.size(); ++i) {
        g[X[i]].pb(Y[i]), g[Y[i]].pb(X[i]);
        e.pb({X[i], Y[i]});
    }
    build_reachability_tree();
    for(int i = 0; i < q; ++i)
        qs[i] = {L[i], R[i], S[i], E[i], i};
    sort(qs, qs + q);
    for(int i = 0, ptr = 0; i < q; ++i) {
        while(ptr < n && ptr <= qs[i].r)
            add(ptr++);
        int p = getk(qs[i].s, qs[i].l);
        set <int>::iterator it = is[s.find(qs[i].e)].lower_bound(tin[p]);
        ans[qs[i].ind] = (it != is[s.find(qs[i].e)].end() && *it <= tout[p]);
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void build_reachability_tree()':
werewolf.cpp:163:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < e.size(); ++i) {
                    ~~^~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:191:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < X.size(); ++i) {
                    ~~^~~~~~~~~~

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