제출 #791315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791315		ilia_rr	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2069 ms	122264 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];

map <int, int> s[N];

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++)
    {
        s[i][i] = 0;

        for (auto [x, y] : s[i])
            f[i].pb({y, x});

        sort(f[i].begin(), f[i].end(), [](ai(2) a, ai(2) b){return a[0] > b[0];});

        if (sz(f[i]) > sq)
            f[i].resize(sq);

        for (auto j : g[i])
            for (auto [l, k] : f[i])
                s[j][k] = max(s[j][k], l + 1);
    }

    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
        {
            map <int, bool> mp;

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

            for (auto [l, k] : f[u])
            {
                if (!mp[k])
                {
                    cout << l << el;
                    
                    goto done;
                }
            }

            cout << -1 << el;

            done:;
        }
    }
}

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