Submission #1115600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115600		LonlyR	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1361 ms	127788 KiB

bitaro

#include<bits/stdc++.h>
#define ii pair<int,int>

using namespace std;
const int maxn = 2e5 + 5, bl = 100;
int n, m, q;
int dp[maxn], mark[maxn];
vector<int> adj[maxn], radj[maxn];
vector<ii> path[maxn];

void precompute()
{
    memset(mark, -1, sizeof mark);
    for (int i = 1; i <= n; i++)
    {
        priority_queue<ii, vector<ii>, greater<ii>> pq;
        pq.emplace(0, i);
        vector<int> cand;
        for (int j : adj[i])
        {
            for (auto [u, v] : path[j])
            {
                u++;
                if (mark[v] == -1)
                    cand.emplace_back(v);
                mark[v] = max(mark[v], u);
            }
        }
        for (int j : cand)
        {
            pq.emplace(mark[j], j);
            if (pq.size() > bl)
                pq.pop();
        }
        while (pq.size())
            path[i].emplace_back(pq.top()),
            pq.pop();
        reverse(path[i].begin(), path[i].end());
        for (int j : cand)
            mark[j] = -1;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> m >> q;
    for (int i = 1, u, v; i <= m; i++)
        cin >> u >> v,
        adj[v].emplace_back(u),
        radj[u].emplace_back(v);
    precompute();
    memset(mark, 0, sizeof mark);
    while (q--)
    {
        int T, k, x, ans = -1;
        cin >> T >> k;
        vector<int> qr;
        while (k--)
            cin >> x, qr.emplace_back(x), mark[x] = 1;
        if (qr.size() >= bl)
        {
            for (int i = 0; i <= n; i++)
                dp[i] = -2e9;
            int oo = dp[0];
            dp[T] = 0;
            for (int i = n; i >= 1; i--)
            {
                for (int j : radj[i]) if (dp[j] != oo)
                    dp[i] = max(dp[i], dp[j] + 1);
                if (dp[i] != oo && !mark[i])
                    ans = max(ans, dp[i]);
            }
        } else
        {
            for (auto [u, v] : path[T])
                if (!mark[v])
                {
                    ans = u;
                    break;
                }
        }
        cout << ans << "\n";
        for (int i : qr) mark[i] = 0;
    }
}

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