Submission #1354651

#TimeUsernameProblemLanguageResultExecution timeMemory
1354651HossamHero7Bitaro’s Party (JOI18_bitaro)C++20
7 / 100
2100 ms244148 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 1e5 + 5 , B = 320;
vector<int> adj[N];
vector<pair<int,int>> dp[N];
void solve(int node){
    if(dp[node].size()) return;
    for(auto ch : adj[node]) solve(ch);
    unordered_map<int,int> mp;
    mp[node] = 0;
    for(auto ch : adj[node]){
        for(auto [d,x] : dp[ch]) mp[x] = max(mp[x] , d + 1);
    }
    for(auto [u,x] : mp){
        dp[node].push_back({x,u});
    }
    sort(dp[node].rbegin(),dp[node].rend());
    while(dp[node].size() > B+1) dp[node].pop_back();
}
bool mark[N];
int dp2[N];
int solve2(int node){
    int &ret = dp2[node];
    if(ret != -1) return dp2[node];
    ret = (mark[node] ? -1e9 : 0);
    for(auto ch : adj[node]){
        ret = max(ret , solve2(ch) + 1);
    }
    return ret;
}
void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<int> deg(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        deg[a] ++;
        adj[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        if(deg[i]) continue;
        solve(i);
    }
    while(q--){
        int node,sz;
        cin>>node>>sz;
        vector<int> v(sz);
        for(auto &i:v) cin>>i;
        if(sz <= B){
            for(auto i : v) mark[i] = 1;
            for(auto [d,x] : dp[node]){
                if(mark[x]) continue;
                cout<<d<<endl;
                goto gt;
            }
            cout<<-1<<endl;
            gt:
            for(auto i : v) mark[i] = 0;
        }
        else {
            memset(dp2,-1,sizeof(dp2));
            for(auto i : v) mark[i] = 1;
            cout<<(solve2(node)<0?-1:solve2(node))<<endl;
            for(auto i : v) mark[i] = 0;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...