Submission #1183238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183238		GGOSHAB	Bitaro’s Party (JOI18_bitaro)	C++20	7 / 100	2092 ms	11376 KiB

bitaro

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#ifndef ONPC
    #pragma GCC target("avx")
    #pragma GCC target("popcnt")

    #define cerr if (false) cerr
#endif

using namespace std;

#define all(v) begin(v), end(v)
#define watch(x) cerr << #x << ": " << x << endl;

typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;

mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l = LLONG_MIN, ll r = LLONG_MAX) {
    return uniform_int_distribution<ll>(l, r)(gen64);
}

template<class T>
bool umin(T &a, const T &b) {
    return (a > b ? a = b, true : false);
}

template<class T>
bool umax(T &a, const T &b) {
    return (a < b ? a = b, true : false);
}

const int mod = 998244353;

ll mult(ll a, ll b) {
    return (a * b) % mod;
}

template<class T>
void add(T &a, const T &b) {
    a = (a + b) % mod;
}

const int inf = int(1e9) + 10;
const ll INF = ll(1e18) + 10;

const int maxn = 2e5 + 10, maxc = 10;
constexpr int sqn = 100;

vector<int> g[maxn];

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int e = 0; e < m; ++e) {
        int v, u;
        cin >> v >> u; v--, u--;
        g[v].push_back(u);
    }

    vector<set<Pint>> small(n);
    vector<map<int, int>> mp(n);
    auto insert = [&](int i, Pint x) {
        auto &m = mp[i];
        auto &s = small[i];
        if (m.count(x.second)) {
            if (m[x.second] > x.first) {
                return;
            }
        }
        s.insert(x);
        m[x.second] = x.first;
        if (s.size() > sqn) {
            m.erase(s.begin()->second);
            s.erase(s.begin());
        }
    };

    for (int i = 0; i < n; ++i) {
//        small[i].push_back({0, i});
        insert(i, {0, i});
    }

    for (int v = 0; v < n; ++v) {
//        sort(all(small[v]), greater<>());
//        if (small[v].size() > sqn) {
//            small[v].resize(sqn);
//        }
        for (int u : g[v]) {
            for (auto [l, p] : small[v]) {
                insert(u, {l + 1, p});
//                small[u].push_back({l + 1, p});
            }
        }
    }

    vector<bool> used(n);
    vector<int> dp(n);
    auto calc_big = [&](int t) {
        for (int i = 0; i < n; ++i) {
            dp[i] = (used[i] ? -inf : 0);
        }
        for (int v = 0; v < n; ++v) {
            for (int u : g[v]) {
                umax(dp[u], dp[v] + 1);
            }
        }

        return max(dp[t], -1);
    };

    while (q--) {
        int t, y;
        cin >> t >> y; t--;
        vector<int> c(y);
        for (auto &v : c) {
            cin >> v; v--;
        }

        for (auto v : c) {
            used[v] = true;
        }

        if (y < sqn) {
            int ans = -1;
            for (auto [l, v] : small[t]) {
                if (!used[v]) {
                    umax(ans, l);
                }
            }

            cout << ans << '\n';
        } else {
            cout << calc_big(t) << '\n';
        }

        for (auto v : c) {
            used[v] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

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