제출 #1133774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133774		Nelt	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1362 ms	520676 KiB

bitaro

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll B = 320, N = 1e5 + 5;
vector<ll> g[N], gr[N];
vector<pair<ll, ll>> best[N];
bool used[N], us[N];
ll dp[N];
vector<ll> top;
void dfs(ll v)
{
    used[v] = 1;
    vector<pair<ll, ll>> tmp;
    best[v].push_back(make_pair(0, v));
    for (ll to : gr[v])
    {
        if (!used[to]) dfs(to);
        tmp.clear();
        ll i = 0, j = 0;
        while (tmp.size() < B + 1)
        {
            while (i < best[v].size() and us[best[v][i].second]) i++;
            while (j < best[to].size() and us[best[to][j].second]) j++;
            if (i == best[v].size() and j == best[to].size()) break;
            if (i == best[v].size())
                tmp.push_back(make_pair(best[to][j].first + 1, best[to][j].second)), j++;
            else if (j == best[to].size())
                tmp.push_back(best[v][i]), i++;
            else if (best[v][i].first < best[to][j].first + 1) tmp.push_back(make_pair(best[to][j].first + 1, best[to][j].second)), j++;
            else tmp.push_back(best[v][i]), i++;
            us[tmp.back().second] = 1;
        }
        best[v] = tmp;
        for (auto i : best[v]) us[i.second] = 0; 
    }
}
void solve()
{
    ll n, m, q;
    cin >> n >> m >> q;
    while (m--)
    {
        ll a, b;
        cin >> a >> b;
        g[a].push_back(b);
        gr[b].push_back(a);
    }
    for (ll i = 1; i <= n; i++) if (!used[i]) dfs(i);
    while (q--)
    {
        ll t, k;
        cin >> t >> k;
        ll x[k];
        for (ll i = 0; i < k; i++)
            cin >> x[i], us[x[i]] = 1;
        ll ans = -1;
        if (k <= B)
        {
            for (auto i : best[t])
                if (!us[i.second])
                {
                    ans = i.first;
                    break;
                }
        }
        else
        {
            for (ll i = 1; i <= n; i++) dp[i] = -1e9;
            dp[t] = 0;
            for (ll i = t; i >= 1; i--)
            {
                for (ll j : g[i]) dp[i] = max(dp[i], dp[j] + 1);
                if (!us[i]) ans = max(ans, dp[i]);
            }
        }
        for (ll i = 0; i < k; i++) us[x[i]] = 0;
        cout << ans << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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