Submission #791332

#	Time	Username	Problem	Language	Result	Execution time	Memory
791332		ilia_rr	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	435 ms	524288 KiB

bitaro

// بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
// Written by Ilia Rahbar

// #pragma GCC optimize ("O3,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target ("abm,bmi,bmi2,tbm,avx2")

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define sz(x) int(x.size())
#define ai(x) array <int, x>
#define be(x) x.begin(), x.end()
#define pb push_back
#define el '\n'
#define sp ' '
#define fi first 
#define se second

const int M = 1e9 + 7, N = 1e6 + 100;

int n, m, q, u, v, t, sq = 400, dp[N];

bool av[N];

vector <int> g[N];

vector <ai(2)> f[N], uni;

void mrg(vector <ai(2)> &a, vector <ai(2)> &b)
{
    uni.clear();

    for (int p1 = 0, p2 = 0; p1 < sz(a) || p2 < sz(b); )
    {
        if (p1 < sz(a))
        {
            if (p2 < sz(b))
            {
                if (a[p1][1] == b[p2][1])
                    uni.pb(max(a[p1++], b[p2++]));

                else if (a[p1][0] > b[p2][0])
                    uni.pb(a[p1++]);

                else
                    uni.pb(b[p2++]);
            }

            else
                uni.pb(a[p1++]);
        }

        else
            uni.pb(b[p2++]);
    }

    if (sz(uni) > sq)
        uni.resize(sq);
}   

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> q;

    while (m--)
        cin >> u >> v, g[u].pb(v);

    for (int i = 1; i <= n; i++)
    {
        f[i].pb({0, i});

        for (int j = 0; j < sz(f[i]); j++)
            f[i][j][0]++;

        for (auto j : g[i])
        {
            mrg(f[i], f[j]);

            f[j] = uni;
        }

        for (int j = 0; j < sz(f[i]); j++)
            f[i][j][0]--;
    }

    while (q--)
    {
        cin >> u >> t;

        if (t >= sq)
        {
            for (int i = 1; i <= u; i++)
                av[i] = 1, dp[i] = -M;

            for (int i = 0; i < t; i++)
                cin >> v, av[v] = 0;

            for (int i = 1; i <= u; i++)
            {
                if (av[i])
                    dp[i] = max(dp[i], int(0));

                for (auto j : g[i])
                    dp[j] = max(dp[j], dp[i] + 1);
            }

            cout << (dp[u] < 0 ? -1 : dp[u]) << el;
        }

        else
        {
            for (auto [x, y] : f[u])
                av[y] = 1;

            for (int i = 0; i < t; i++)
                cin >> v, av[v] = 0;

            for (auto [x, y] : f[u])
                if (av[y])
                {
                    cout << x << el;

                    goto done;
                }

            cout << -1 << el;
            
            done:;
        }
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86