제출 #1331146

#제출 시각아이디문제언어결과실행 시간메모리
1331146AgageldiBitaro’s Party (JOI18_bitaro)C++20
100 / 100
1341 ms280012 KiB
#include <bits/stdc++.h>
using namespace std;

#define N 200001

const int inf = INT_MAX;
const int M = 998244353;

int n, c, m, T[N], Y[N], Q, dp[N], jog[N];
vector <pair<int,int>> q, L[N];
vector <int> E[N], R[N];
set <int> C[N];

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m >> Q;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        R[v].push_back(u);
        E[u].push_back(v);
    }
    int B = sqrt(n);
    for(int i = 1; i <= Q; i++) {
        cin >> T[i] >> Y[i];
        for(int j = 1; j <= Y[i]; j++) {
            int nd;
            cin >> nd;
            C[i].insert(nd);
        }
        q.push_back({Y[i], i});
    }
    vector<int> M(n+1,0), bd(n+1,-1), t;

    for (int i=1;i<=n;i++){
        t.clear();

        auto add = [&](int src, int d){
            if (M[src] != i){
                M[src] = i;
                bd[src] = d;
                t.push_back(src);
            } else bd[src] = max(bd[src], d);
        };

        add(i, 0);
        for (int p : R[i]) {
            for (auto [d, s] : L[p]) add(s, d + 1);
        }

        vector<pair<int,int>> v;
        for (int s : t) v.push_back({bd[s], s});
        sort(v.begin(), v.end(), greater<pair<int,int>>());
        if ((int)v.size() > B) v.resize(B);
        L[i] = v;
    }

    sort(q.rbegin(),q.rend());
    
    for(auto [y, id] : q) {
        if(y >= B) {
            for(int j = n; j >= 1; j--) {
                dp[j] = inf;
            }
            dp[T[id]] = 0;
            for(int j = n; j >= 1; j--) {
                if(j == T[id]) continue;
                int bs = -1;
                for(auto i : E[j]) {
                    if(dp[i] != inf) bs = max(bs, dp[i]);
                }
                if(bs != -1) dp[j] = bs + 1;
            }
            int ans = -1;
            for(int j = n; j >= 1; j--) {
                if(dp[j] == INT_MAX) continue;
                if(C[id].find(j) == C[id].end()) {
                    ans = max(ans, dp[j]);
                }
            }
            jog[id] = ans;
        }
        else {
            bool ok = 0;
            for(auto j : L[T[id]]) {
                if(C[id].find(j.second) == C[id].end()) {
                    jog[id] = j.first;
                    ok = 1;
                    break;
                }
            }
            if(!ok) jog[id] = -1;
        }
    }
    for(int i = 1; i <= Q; i++) {
        cout << jog[i] << endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...