제출 #1093228

#제출 시각아이디문제언어결과실행 시간메모리
1093228davieduBitaro’s Party (JOI18_bitaro)C++17
14 / 100
2058 ms137296 KiB
#include <bits/stdc++.h>
using namespace std;

#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int) (a).size()
#define ll long long
#define ld long double
#define pb push_back

struct P{
    ll x, y;
};

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

const int mx=1e5+1;
const int k=100;
vector<int> g[mx];
vector<pair<int, int>> best[mx];
int blocked[mx];

signed main(){
    fastio;
    int n, m, q;
    cin >> n >> m >> q;
    for (int i=0; i<m; i++){
        int a, b;
        cin >> a >> b;
        g[b].push_back(a);
    }
    map<int, int> cur;
    for (int i=1; i<=n; i++){
        cur[i] = 0;
        for (auto u: g[i]){
            for (const auto& [b, d]: best[u]){
                cur[b] = max(cur[b], d+1);
            }
        }
        for (const auto& [b, d]: cur) best[i].push_back({d, b});
        sort(rall(best[i]));
        best[i].resize(min(k, sz(best[i])));
        for (auto& [d, b]: best[i]) swap(d, b);
        cur.clear();
    }
    vector<int> dp (n+1);
    stack<int> removed;
    while (q--){
        int city, y;
        cin >> city >> y;
        while (y--){
            int x; cin >> x;
            removed.push(x);
            blocked[x] = 1;
        }

        int ans=-1;
        if (sz(removed) < k){
            for (const auto& [b, d]: best[city]){
                if (!blocked[b]){
                    ans = d;
                    break;
                }
            }
        }
        else{
            for (int i=city; i; i--){
                if (!dp[i] && i != city) continue;
                for (auto u: g[i]) dp[u] = max(dp[u], dp[i]+1);
                if (!blocked[i]) ans = max(ans, dp[i]);
            }
            for (int i=city; i; i--) dp[i] = 0;
        }
        cout << ans << '\n';

        while (!removed.empty()){
            blocked[removed.top()] = 0;
            removed.pop();
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...