Submission #1087157

#TimeUsernameProblemLanguageResultExecution timeMemory
1087157GrayBitaro’s Party (JOI18_bitaro)C++17
14 / 100
605 ms246636 KiB
    #include <bits/stdc++.h>
    #define ll int
    #define ld long double
    #define ff first
    #define ss second
    #define ln "\n"
    using namespace std;
     
    const ll INF = 2e18;
    const ll MOD = (ll)1e9+7;
     
    const ll B = 100;
     
    ll n, m, q;
    vector<vector<ll>> A;
     
    void bdfs(ll u, vector<ll> &dp, set<ll> &blocked){
    	dp[u]=0;
    	for (auto v:A[u]){
    		if (dp[v]==-1){
    			bdfs(v, dp, blocked);
    		}
    		dp[u]=max(dp[u], dp[v]+1);
    	}
    	if (dp[u]==0 and blocked.count(u)){
    		dp[u]=-INF;
    	}
    }
     
    ll brute(ll u, set<ll> &block){
    	vector<ll> dp(n+1, -1);
    	bdfs(u, dp, block);
    	return dp[u]==-INF?-1:dp[u];
    }
     
    vector<vector<pair<ll, ll>>> dp;
     
    void append(pair<ll, ll> x, vector<pair<ll, ll>> &st){
    	st.push_back(x);
    }
     
    void dfs(ll u, vector<bool> &vis){
    	vis[u]=1;
    	for (auto v:A[u]){
    		if (!vis[v]) dfs(v, vis);
    		for (auto ch:dp[v]){
    			append({ch.ff+1, ch.ss}, dp[u]);
    		}
    	}
    	append({0, u}, dp[u]);
    	sort(dp[u].rbegin(), dp[u].rend());
    	while (dp[u].size()>B) dp[u].pop_back();
    	reverse(dp[u].begin(), dp[u].end());
    }
     
    void solve(){
    	cin >> n >> m >> q;
    	A.resize(n+1);
    	for (ll i=0; i<m; i++){
    		ll u, v; cin >> u >> v;
    		A[v].push_back(u);
    	}
    	dp.resize(n+1);
    	vector<bool> vis(n+1);
    	for (ll i=1; i<=n; i++){
    		if (!vis[i]) dfs(i, vis);
    	}
    	while (q--){
    		ll t, y; cin >> t >> y;
    		set<ll> blocked;
    		for (ll i=0; i<y; i++){
    			ll x; cin >> x; blocked.insert(x);
    		}
    		if (y<B){
    			ll mx=-1;
    			for (auto ch:dp[t]){
    				if (!blocked.count(ch.ss)) mx=max(mx, ch.ff);
    			}
    			cout << mx << ln;
    		}else{
    			cout << brute(t, blocked) << ln;
    		}
    	}
    }
     
     
    int main(){
    	ios_base::sync_with_stdio(0);
    	cin.tie(nullptr);
    	ll t=1;
    	// cin >> t;
    	while (t--) solve();
    }

Compilation message (stderr)

bitaro.cpp:9:20: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
    9 |     const ll INF = 2e18;
      |                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...