제출 #1133753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133753		Nelt	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	26 ms	14152 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();
        for (auto i : best[v]) tmp.push_back(i);
        for (auto i : best[to]) tmp.push_back(make_pair(i.first + 1, i.second));
        sort(tmp.begin(), tmp.end(), greater());
        best[v].clear();
        for (auto i : tmp) if (!us[i.second] and best[v].size() < B + 1) best[v].push_back(i), us[i.second] = 1;
        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;
        set<ll> s;
        for (ll i = 0; i < k; i++)
        {
            ll x;
            cin >> x;
            s.insert(x);
        }
        ll ans = -1;
        if (k <= B)
        {
            for (auto i : best[t])
                if (!s.count(i.second))
                {
                    ans = i.first;
                    break;
                }
        }
        else
        {
            for (ll i = 1; i <= n; i++) dp[i] = -1e9;
            dp[t] = 0;
            for (ll i = t - 1; i >= 1; i--)
            {
                for (ll j : g[i]) dp[i] = max(dp[i], dp[j] + 1);
                if (!s.count(i)) ans = max(ans, dp[i]);
            }
        }
        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: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86