Submission #944020

#	Time	Username	Problem	Language	Result	Execution time	Memory
944020		RadicaI	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2075 ms	25772 KiB

bitaro

#include <bits/stdc++.h>
#define int long long
#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;
const int mxn = 1e5+1;
v2i adj(mxn);
V<set<pi>> mx(mxn);
 
signed main(){
	fastio;
	int n,m,q; cin>>n>>m>>q;
	for(int i=0; i<m; i++){
		int s,e; cin>>s>>e; s--;e--;
		adj[e].pb(s);
	}
	for(int i=0; i<n; i++){
		mx[i].ins({0,i});
		map<int,si> jhxt;
		for(auto &x: adj[i]){
			for(auto &y: mx[x]){
				jhxt[y.S].ins(y.F+1);
			}
		}
		for(auto &x: jhxt){
			mx[i].ins({*x.S.rbegin(), x.F}); 
			if(sz(mx[i])>block) mx[i].erase(mx[i].begin());
		}
	}
	vi store(n, q+1);
	vi dp;
	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){
			dp  = vi(t+1,-1);
			for(int i=0; i<=t; i++){
				if(store[i]!=q)dp[i]=max(dp[i],0ll);
				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;
		}
	}
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86