oj.uz

Submission #896696

# Submission time Handle Problem Language Result Execution time Memory
896696 2024-01-01T21:45:55 Z Nelt Werewolf (IOI18_werewolf) C++17
100 / 100
 864 ms 192244 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 44124 KB Output is correct
2 Correct 11 ms 44216 KB Output is correct
3 Correct 11 ms 44312 KB Output is correct
4 Correct 9 ms 44124 KB Output is correct
5 Correct 11 ms 44120 KB Output is correct
6 Correct 9 ms 44124 KB Output is correct
7 Correct 9 ms 44120 KB Output is correct
8 Correct 10 ms 44124 KB Output is correct
9 Correct 10 ms 44124 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 44124 KB Output is correct
2 Correct 11 ms 44216 KB Output is correct
3 Correct 11 ms 44312 KB Output is correct
4 Correct 9 ms 44124 KB Output is correct
5 Correct 11 ms 44120 KB Output is correct
6 Correct 9 ms 44124 KB Output is correct
7 Correct 9 ms 44120 KB Output is correct
8 Correct 10 ms 44124 KB Output is correct
9 Correct 10 ms 44124 KB Output is correct
10 Correct 15 ms 46168 KB Output is correct
11 Correct 14 ms 45916 KB Output is correct
12 Correct 17 ms 46320 KB Output is correct
13 Correct 15 ms 46172 KB Output is correct
14 Correct 16 ms 46076 KB Output is correct
15 Correct 15 ms 46172 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 179768 KB Output is correct
2 Correct 440 ms 183604 KB Output is correct
3 Correct 436 ms 180092 KB Output is correct
4 Correct 558 ms 181304 KB Output is correct
5 Correct 609 ms 180464 KB Output is correct
6 Correct 671 ms 180144 KB Output is correct
7 Correct 497 ms 176696 KB Output is correct
8 Correct 429 ms 183860 KB Output is correct
9 Correct 474 ms 179960 KB Output is correct
10 Correct 403 ms 178572 KB Output is correct
11 Correct 413 ms 180536 KB Output is correct
12 Correct 564 ms 181040 KB Output is correct
13 Correct 551 ms 191536 KB Output is correct
14 Correct 579 ms 191028 KB Output is correct
15 Correct 560 ms 190888 KB Output is correct
16 Correct 558 ms 190904 KB Output is correct
17 Correct 492 ms 177448 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 44124 KB Output is correct
2 Correct 11 ms 44216 KB Output is correct
3 Correct 11 ms 44312 KB Output is correct
4 Correct 9 ms 44124 KB Output is correct
5 Correct 11 ms 44120 KB Output is correct
6 Correct 9 ms 44124 KB Output is correct
7 Correct 9 ms 44120 KB Output is correct
8 Correct 10 ms 44124 KB Output is correct
9 Correct 10 ms 44124 KB Output is correct
10 Correct 15 ms 46168 KB Output is correct
11 Correct 14 ms 45916 KB Output is correct
12 Correct 17 ms 46320 KB Output is correct
13 Correct 15 ms 46172 KB Output is correct
14 Correct 16 ms 46076 KB Output is correct
15 Correct 15 ms 46172 KB Output is correct
16 Correct 557 ms 179768 KB Output is correct
17 Correct 440 ms 183604 KB Output is correct
18 Correct 436 ms 180092 KB Output is correct
19 Correct 558 ms 181304 KB Output is correct
20 Correct 609 ms 180464 KB Output is correct
21 Correct 671 ms 180144 KB Output is correct
22 Correct 497 ms 176696 KB Output is correct
23 Correct 429 ms 183860 KB Output is correct
24 Correct 474 ms 179960 KB Output is correct
25 Correct 403 ms 178572 KB Output is correct
26 Correct 413 ms 180536 KB Output is correct
27 Correct 564 ms 181040 KB Output is correct
28 Correct 551 ms 191536 KB Output is correct
29 Correct 579 ms 191028 KB Output is correct
30 Correct 560 ms 190888 KB Output is correct
31 Correct 558 ms 190904 KB Output is correct
32 Correct 492 ms 177448 KB Output is correct
33 Correct 658 ms 180272 KB Output is correct
34 Correct 195 ms 85764 KB Output is correct
35 Correct 640 ms 184024 KB Output is correct
36 Correct 626 ms 180408 KB Output is correct
37 Correct 664 ms 183900 KB Output is correct
38 Correct 654 ms 181572 KB Output is correct
39 Correct 864 ms 189148 KB Output is correct
40 Correct 604 ms 189548 KB Output is correct
41 Correct 555 ms 181816 KB Output is correct
42 Correct 406 ms 179096 KB Output is correct
43 Correct 581 ms 189636 KB Output is correct
44 Correct 625 ms 182132 KB Output is correct
45 Correct 556 ms 189804 KB Output is correct
46 Correct 444 ms 188728 KB Output is correct
47 Correct 574 ms 191288 KB Output is correct
48 Correct 542 ms 191796 KB Output is correct
49 Correct 546 ms 192056 KB Output is correct
50 Correct 564 ms 192244 KB Output is correct
51 Correct 586 ms 189788 KB Output is correct
52 Correct 529 ms 190264 KB Output is correct