Submission #791346

#	Time	Username	Problem	Language	Result	Execution time	Memory
791346		ilia_rr	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	753 ms	293336 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, ans, v, vs[N], t, sq = 100, dp[N];

bool av[N];

vector <int> g[N], in;

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][0] > b[p2][0])
                    uni.pb(a[p1++]);

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

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

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

    b.clear();

    for (auto [x, y] : uni)
        if (!vs[y])
            vs[y] = 1, b.pb({x, y});

    for (auto [x, y] :  uni)
        vs[y] = 0;

    if (sz(b) > sq)
        b.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 i = 1; i <= n; i++)
    {
        for (int j = 0; j < sz(f[i]); j++)
            f[i][j][0]++;

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

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

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

        in.clear();
            
        ans = -1;

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

        for (auto [x, y] : f[u])
            if (!av[y])
            {
                ans = x;
                
                break;
            }

        if (t >= sq && ans == -1)
        {
            fill(dp, dp + u + 1, -M);

            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);
            }
        
            ans = dp[u];
        }

        cout << (ans < 0 ? -1 : ans) << el;

        for (auto i : in)
            av[i] = 0;
    }
}

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