Submission #1341603

#TimeUsernameProblemLanguageResultExecution timeMemory
1341603Born_To_LaughBitaro’s Party (JOI18_bitaro)C++17
14 / 100
995 ms216456 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;

const int maxn = 1e5 + 10;
const int sq = 320;
int n, m, q, vis[maxn], added[maxn], rem[maxn];
vector<int> adj[maxn], radj[maxn];
vector<pair<int, int>> li[maxn];
vector<int> topo;

void dfs(int a){
    vis[a] = 1;
    for(auto &elm: adj[a]) if(!vis[elm]) dfs(elm);
    topo.push_back(a);
}
void buildli(){
    for(auto &a: topo){
        priority_queue<pair<pair<int,int>,pair<int,int>>> pq;
        for(auto &elm: radj[a]){
            pq.push({li[elm][0], {elm, 0}});
        }
        for(int i=1; i<=320 && !pq.empty(); ++i){
            auto x = pq.top();
            pq.pop();
            if(!added[x.fi.se]){
                li[a].push_back({x.fi.fi + 1, x.fi.se});
                added[x.fi.se] = 1;
            }
            if(li[x.se.fi].size() > x.se.se + 1){
                pq.push({li[x.se.fi][x.se.se + 1], {x.se.fi, x.se.se + 1}});
            }
        }
        if(li[a].size() < 320) li[a].push_back({0, a});
        for(auto &elm: li[a]) added[elm.se] = 0;
    }
}

int ope1(int x, int y, vector<int> &sth){
    for(auto &elm: sth) rem[elm] = 1;
    int ans = -1;
    for(auto &elm: li[x]){
        if(rem[elm.se]) continue;
        ans = elm.fi;break;
    }
    for(auto &elm: sth) rem[elm] = 0;
    return ans;
}


int ope2(int x, int y, vector<int> &sth){
    for(auto &elm: sth) rem[elm] = 1;
    vector<int> dp(n + 1, -INF);
    dp[x] = 0;
    int ans = -1;
    for(int i = n - 1; i>=0; --i){
        int a = topo[i];
        for(auto &elm: adj[a]){
            dp[a] = max(dp[a], dp[elm] + 1);
        }
        if(!rem[a]) ans = max(ans, dp[a]);
    }
    for(auto &elm: sth) rem[elm] = 0;
    return ans;
}

void solve(){
    cin >> n >> m >> q;
    for(int i=1; i<=m; ++i){
        int a, b;cin >> a >> b;
        adj[a].push_back(b);
        radj[b].push_back(a);
    }
    for(int i=1; i<=n; ++i) if(!vis[i]) dfs(i);
    reverse(alle(topo));
    buildli();
    while(q--){
        int x, y;cin >> x >> y;
        vector<int> sth(y);
        for(int i=0; i<y; ++i) cin >> sth[i];
        if(y < 320){
            cout << ope1(x, y, sth) << '\n';
        }
        else{
            cout << ope2(x, y, sth) << '\n';
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...