제출 #1342380

#제출 시각아이디문제언어결과실행 시간메모리
1342380PakinDioxideBitaro’s Party (JOI18_bitaro)C++17
100 / 100
884 ms143664 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 1e5+5;

int n, m, q, k, ok[mxN];
vector <pair <int, int>> dp[mxN];
vector <int> adj[mxN], mx(mxN, -1);

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> q; k = 100;
    for (int i = 0, u, v; i < m; i++) cin >> u >> v, adj[max(u, v)].emplace_back(min(u, v));
    for (int u = 1; u <= n; u++) {
        vector <int> vis;
        dp[u].emplace_back(0, u);
        for (auto v : adj[u]) for (auto &[val, idx] : dp[v]) {
            if (mx[idx] == -1) {
                vis.emplace_back(idx);
                mx[idx] = val+1;
            } else {
                mx[idx] = max(mx[idx], val+1);
            }
        }
        for (auto &e : vis) dp[u].emplace_back(mx[e], e);
        sort(dp[u].rbegin(), dp[u].rend());
        while ((int) dp[u].size() > k) dp[u].pop_back();
        for (auto &e : vis) mx[e] = -1;
    }
    while (q--) {
        int u, y; cin >> u >> y;
        vector <int> X;
        for (int i = 0, e; i < y; i++) { cin >> e; if (e <= u) X.emplace_back(e), ok[e] = 1; }
        y = X.size();
        if (y < k) {
            int ans = -1;
            for (auto &[val, idx] : dp[u]) if (!ok[idx]) { ans = val; break; }
            cout << ans << '\n';
        } else {
            vector <int> DP(n+1, INT_MIN);
            for (int i = 1; i <= u; i++) { if (!ok[i]) DP[i] = 0; for (auto v : adj[i]) DP[i] = max(DP[i], DP[v]+1); }
            cout << max(-1, DP[u]) << '\n';
        }
        for (auto &e : X) ok[e] = 0;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...