Submission #944018

#TimeUsernameProblemLanguageResultExecution timeMemory
944018RadicaIBitaro’s Party (JOI18_bitaro)C++17
7 / 100
2100 ms15896 KiB
    #include <bits/stdc++.h>
    #define pi pair<int,int>
    #define pb push_back
    #define V vector
    #define vi V<int>
    #define mi map<int,int>
    #define MOD 1000000007
    #define MOD2 998244353
    #define mp make_pair
    #define ins insert
    #define qi queue<int>
    #define pqi priority_queue<int>
    #define si set<int>
    #define v2i V<vi>
    #define v3i V<v2i>
    #define v4i V<v3i>
    #define v5i V<v4i>
    #define INF 1e18
    #define all(x) begin(x), end(x)
    #define sz(x) (int) (x).size()
    #define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #define endl "\n"
    #define lb lower_bound
    #define ub upper_bound
    #define print(x) cout << x<<" ";
    #define vpi V<pi>
    #define Y cout<<"YES"<<endl;
    #define NO cout<<"NO"<<endl;
    #define msi multiset<int>
    #define F first
    #define S second
    #define ld long double
    #define RE return;
    #define IMP cout<<-1<<endl;return;
    using namespace std;
     
    template <typename T>
    std::istream& operator>>(std::istream& in, std::vector<T>& vec) {
        for (T& x : vec) {
            in >> x;
        }
        return in;
    }
     
    const int block = 350;
     
     
    signed main(){
    	fastio;
    	int n,m,q; cin>>n>>m>>q;
    	v2i adj(n); 
    	for(int i=0; i<m; i++){
    		int s,e; cin>>s>>e; s--;e--;
    		adj[e].pb(s);
    	}
    	V<set<pi>> mx(n); 
    	for(int i=0; i<n; i++){
    		mx[i].ins({0,i});
    		map<int,vi> jhxt;
    		for(auto &x: adj[i]){
    			for(auto &y: mx[x]){
    				jhxt[y.S].pb(y.F+1);
    			}
    		}
    		for(auto &x: jhxt){
    			sort(all(x.S));
    			mx[i].ins({x.S.back(), x.F}); 
    			if(sz(mx[i])>block) mx[i].erase(mx[i].begin());
    		}
    	}
    	vi store(n, q+1);
    	while(q--){
    		int t,y; cin >> t>>y; 
    		t--; 
    		for(int i=0; i<y; i++){int x; cin >> x; store[x-1]=q;}
    		if(y>=block){
    			vi dp(t+1,-1);
    			for(int i=0; i<=t; i++){
    				if(store[i]!=q)dp[i]=max(dp[i],0);
    				for(auto &x: adj[i]){
    					if(dp[x]!=-1)dp[i] = max(dp[x]+1, dp[i]);
    				}
    			}
    			cout << dp[t]<<endl;
    		}else{
    			int ans = -1;
    			for(auto &x: mx[t])if(store[x.S]!=q) ans = x.F;
    			cout<<ans<<endl;
    		}
    	}
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...