제출 #1342373

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

using namespace std;

const int mxN = 1e5+5;

int n, m, q, k, ok[mxN];
set <pair <int, int>> dp[mxN], dp2[mxN];
vector <int> adj[mxN];

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++) {
        dp[u].emplace(0, u);
        dp2[u].emplace(u, 0);
        for (auto v : adj[u]) for (auto &e : dp[v]) {
            if ((int) dp[u].size() == k && -(*prev(dp[u].end())).first >= -e.first+1) break;
            auto it = dp2[u].upper_bound(make_pair(e.second, INT_MIN));
            if (it != dp2[u].end() && (*it).first == e.second) {
                if ((*it).second > e.first - 1) {
                    dp[u].erase(dp[u].find(make_pair((*it).second, (*it).first)));
                } else continue;
            }
            dp[u].emplace(e.first-1, e.second);
            dp2[u].emplace(e.second, e.first-1);
            if ((int) dp[u].size() > k) {
                dp2[u].erase(dp2[u].find(make_pair((*prev(dp[u].end())).second, (*prev(dp[u].end())).first)));
                dp[u].erase(prev(dp[u].end()));
            }
        }
    }
    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) {
            auto it = dp[u].begin();
            while (it != dp[u].end() && ok[(*it).second]) it++;
            if (it == dp[u].end()) cout << -1 << '\n';
            else cout << -(*it).first << '\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...