Submission #241939

#	Time	Username	Problem	Language	Result	Execution time	Memory
241939		abacaba	Werewolf (IOI18_werewolf)	C++14	0 / 100	3041 ms	524288 KiB

werewolf

#include <iostream>
#include <string>
#include "werewolf.h"
#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 = 4e5 + 15;
const int L = 20;
int n, q;
vector <int> g[N];

int l[N], r[N];

int k[N], tin[N], tout[N], tt, up[L][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];
        }
    }
} dsu, rt;

struct segment_tree {
    multiset <int> t[N << 2];
    void update(int v, int tl, int tr, int pos, int val, int type) {
        if(type == 1)
            t[v].insert(val);
        else
            t[v].erase(t[v].find(val));
        if(tl != tr) {
            int mid = tl + tr >> 1;
            if(pos <= mid)
                update(v << 1, tl, mid, pos, val, type);
            else
                update(v << 1 | 1, mid + 1, tr, pos, val, type);
        }
    }
    bool check(int v, int tl, int tr, int l, int r, int val) {
        if(tl > r || tr < l || l > r)
            return false;
        if(tl >= l && tr <= r)
            return t[v].find(val) != t[v].end();
        int mid = tl + tr >> 1;
        return check(v << 1, tl, mid, l, r, val) || check(v << 1 | 1, mid + 1, tr, l, r, val);
    }
} t;

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++;
        assert(l[v] == -1);
        assert(r[v] == -1);
    }
    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);
    });
    memset(l, -1, sizeof(l));
    memset(r, -1, sizeof(r));
    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)
        t.update(1, 0, n - 1, tin[i], i, 1);
}

inline void add(int v) {
    for(int to : g[v])
        if(to < v) {
            t.update(1, 0, n - 1, tin[v], dsu.find(v), -1);
            t.update(1, 0, n - 1, tin[to], dsu.find(to), -1);
            dsu.unio(to, v);
            t.update(1, 0, n - 1, tin[v], dsu.find(v), 1);
            t.update(1, 0, n - 1, tin[to], dsu.find(to), 1);
        }
}


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);
        ans[qs[i].ind] = t.check(1, 0, n - 1, tin[p], tout[p], dsu.find(qs[i].e));
    }
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In member function 'void segment_tree::update(int, int, int, int, int, int)':
werewolf.cpp:104:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid = tl + tr >> 1;
                       ~~~^~~~
werewolf.cpp: In member function 'bool segment_tree::check(int, int, int, int, int, int)':
werewolf.cpp:116:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = tl + tr >> 1;
                   ~~~^~~~
werewolf.cpp: In function 'void build_reachability_tree()':
werewolf.cpp:165: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:198:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < X.size(); ++i) {
                    ~~^~~~~~~~~~

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