Submission #896696

#	Time	Username	Problem	Language	Result	Execution time	Memory
896696		Nelt	Werewolf (IOI18_werewolf)	C++17	100 / 100	864 ms	192244 KiB

werewolf

#include "werewolf.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define ANDROID                   \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 2e5 + 5;
vv(ll) sufg[N], prefg[N], adj[N], adj1[N];
ll d[N], d1[N], f[N], f1[N];
struct Dsu
{
    ll n, ans;
    vv(ll) dsu;
    Dsu(ll sz = 1)
    {
        n = sz;
        ans = n;
        dsu.resize(n + 1, 0);
        init();
    }
    void init()
    {
        for (ll i = 1; i <= n; i++)
            dsu[i] = -1;
    }
    bool Union(ll x, ll y, bool flg)
    {
        x = repr(x), y = repr(y);
        if (x == y)
            return false;
        if (flg and (x > y))
            swap(x, y);
        if (!flg and (x < y))
            swap(x, y);
        ans--;
        dsu[y] += dsu[x];
        dsu[x] = y;
        return true;
    }
    ll repr(ll x)
    {
        if (dsu[x] < 0)
            return x;
        return dsu[x] = repr(dsu[x]);
    }
    ll query()
    {
        return ans;
    }
    ll size(ll x)
    {
        return -dsu[repr(x)];
    }
};
vv(ll) st[N << 2];
ll sz;
void build()
{
    for (ll i = sz - 1; i >= 1; i--)
        merge(allc(st[i << 1]), allc(st[i << 1 | 1]), back_inserter(st[i]));
}
int query(ll l, ll r, ll l1, ll r1)
{
    ll pos;
    for (l += sz - 1, r += sz; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1)
        {
            if (upper_bound(allc(st[l]), r1) - lower_bound(allc(st[l]), l1) > 0)
                return true;
            l++;
        }
        if (r & 1)
        {
            r--;
            if (upper_bound(allc(st[r]), r1) - lower_bound(allc(st[r]), l1) > 0)
                return true;
        }
    }
    return false;
}
ll timer = 1;
void prefdfs(ll v)
{
    d[v] = timer++;
    for (ll to : prefg[v])
        prefdfs(to);
    f[v] = timer++;
}
void sufdfs(ll v)
{
    d1[v] = timer++;
    for (ll to : sufg[v])
        sufdfs(to);
    f1[v] = timer++;
}
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y, std::vector<int> St, std::vector<int> E, std::vector<int> L, std::vector<int> R)
{
    sz = (n << 1);
    ll q = St.size();
    for (ll i = 0; i < X.size(); i++)
        X[i]++, Y[i]++, adj[min(X[i], Y[i])].pb(max(X[i], Y[i])), adj1[max(X[i], Y[i])].pb(min(X[i], Y[i]));
    vv(pp(ll, ll)) sufproc[n + 1], prefproc[n + 1];
    ll sufrep[q], prefrep[q];
    for (ll i = 0; i < q; i++)
        St[i]++, E[i]++, L[i]++, R[i]++, sufproc[L[i]].pb(mpr(St[i], i)), prefproc[R[i]].pb(mpr(E[i], i));
    Dsu dsu(n);
    for (ll i = 1; i <= n; i++)
    {
        for (ll j : adj1[i])
            if (i != dsu.repr(j))
            {
                prefg[i].pb(dsu.repr(j));
                dsu.Union(i, j, true);
            }
        for (auto [j, ind] : prefproc[i])
            prefrep[ind] = dsu.repr(j);
    }
    dsu = Dsu(n);
    for (ll i = n; i >= 1; i--)
    {
        for (ll j : adj[i])
            if (i != dsu.repr(j))
            {
                sufg[i].pb(dsu.repr(j));
                dsu.Union(i, j, false);
            }
        for (auto [j, ind] : sufproc[i])
            sufrep[ind] = dsu.repr(j);
    }
    timer = 1;
    prefdfs(n);
    timer = 1;
    sufdfs(1);
    for (ll i = sz; i < (sz << 1); i++)
        st[i] = {INF};
    for (ll i = 1; i <= n; i++)
        st[d[i] + sz - 1] = {d1[i]};
    build();
    // cout << "OK\n";
    vv(int) ans;
    // for (ll i = 0; i < q; i++)
    //     cout << d1[sufrep[i]] << " " << f1[sufrep[i]] << endl;
    for (ll i = 0; i < q; i++)
        ans.pb(query(d[prefrep[i]], f[prefrep[i]], d1[sufrep[i]], f1[sufrep[i]]));
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'int query(long long int, long long int, long long int, long long int)':
werewolf.cpp:102:8: warning: unused variable 'pos' [-Wunused-variable]
  102 |     ll pos;
      |        ^~~
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:139:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for (ll i = 0; i < X.size(); i++)
      |                    ~~^~~~~~~~~~

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