Submission #1052966

#TimeUsernameProblemLanguageResultExecution timeMemory
1052966fryingducBitaro’s Party (JOI18_bitaro)C++17
14 / 100
756 ms241488 KiB
#include "bits/stdc++.h"
using namespace std;

const int maxn = 1e5 + 5;
const int B = 200;
int n, m, q;
vector<int> g[maxn];
vector<pair<int, int>> lp[maxn];
int del[maxn], d[maxn], mx[maxn][2];

void dp(int src) {
    for(int i = 0; i <= n; ++i) d[i] = -1;
    for(int i = 1; i <= src; ++i) {
        if(!del[i]) d[i] = 0;
        for(auto u:g[i]) {
            if(d[u] >= 0) d[i] = max(d[i], d[u] + 1);
        }
    }
}
void solve() {
    cin >> n >> m >> q;
    for(int i = 1; i <= m; ++i) {
        int u, v; cin >> v >> u;
        g[u].push_back(v);
    }
    for(int i = 1; i <= n; ++i) {
        vector<int> cur;
        for(auto v:g[i]) {
            for(auto j:lp[v]) {
                if(mx[j.second][1] != i) {
                    cur.push_back(j.second);
                    mx[j.second][1] = i;
                    mx[j.second][0] = j.first + 1;
                }
                else {
                    mx[j.second][0] = max(mx[j.second][0], j.first + 1);
                }
            }
        }
        for(auto j:cur) {
            lp[i].push_back({mx[j][0], j});
        }
        lp[i].push_back({0, i});
        sort(lp[i].begin(), lp[i].end(), greater<pair<int, int>>());
        while((int)lp[i].size() > B) {
            lp[i].pop_back();
        }
    }
    while(q--) {
        int sz, x; cin >> x >> sz;
        vector<int> cur;
        for(int i = 1; i <= sz; ++i) {
            int u; cin >> u;
            cur.push_back(u);
            del[u] = 1;
        }
        if(sz > B) {
            dp(x);
            cout << d[x] << '\n';
        }
        else {
            int res = -1;
            for(int i = 0; i < (int)lp[x].size(); ++i) {
                if(!del[lp[x][i].second]) {
                    res = lp[x][i].first;
                    break;
                }
            }
            
            cout << res << '\n';
        }
        
        for(auto &i:cur) del[i] = 0;
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...