제출 #1331271

#제출 시각아이디문제언어결과실행 시간메모리
1331271Braabebo10Bitaro’s Party (JOI18_bitaro)C++20
100 / 100
1038 ms485080 KiB
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
const ll BLK = 300;

int main() {
    baraa
    ll n, m, q;
    cin >> n >> m >> q;
    vector<ll> adj[n + 1], have(n + 1, 1), vis(n + 1, -1);
    ll vid = 0;
    while (m--) {
        ll u, v;
        cin >> u >> v;
        adj[v].push_back(u);
    }
    vector<array<ll, 2> > vals[n + 1];
    for (ll u = 1; u <= n; u++) {
        for (ll v: adj[u]) {
            auto &a = vals[u];
            auto &b = vals[v];
            vector<array<ll, 2> > res;
            auto push = [&](vector<array<ll, 2> > &c, ll idx) {
                if (vis[c[idx][1]] != vid)res.push_back(c[idx]);
                vis[c[idx][1]] = vid;
            };
            ll sz1 = a.size(), sz2 = b.size(), i = 0, j = 0;
            while ((i < sz1 or j < sz2) and res.size() <= BLK) {
                if (i == sz1)push(b, j++);
                else if (j == sz2 or a[i] > b[j])push(a, i++);
                else push(b, j++);
            }
            vals[u] = res;
            vid++;
        }
        for (auto &[d, _]: vals[u])d++;
        if (vals[u].size() <= BLK)
            vals[u].push_back({0, u});
        // cout << u << nl;
        // for (auto &[d, node]: vals[u])
        //     cout << node << ' ' << d << nl;
    }
    while (q--) {
        ll node, sz;
        cin >> node >> sz;
        vector<ll> nodes(sz);
        for (auto &x: nodes)cin >> x, have[x] = 0;
        ll res = -1;
        if (sz >= BLK) {
            vector<ll> dp(n + 1, -1e12);
            dp[node] = 0;
            for (ll u = node; u >= 1; u--) {
                for (ll v: adj[u])
                    dp[v] = max(dp[v], dp[u] + 1);
                if (have[u])
                    res = max(res, dp[u]);
            }
        } else {
            for (auto [d, u]: vals[node])
                if (have[u]) {
                    res = d;
                    break;
                }
        }
        cout << res << nl;
        for (auto &x: nodes)have[x] = 1;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...