Submission #943822

#	Time	Username	Problem	Language	Result	Execution time	Memory
943822		RadicaI	Bitaro’s Party (JOI18_bitaro)	C++17	0 / 100	14 ms	2964 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;

 
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});
		set<pi> used; 
		for(auto&x: adj[i]){
			for(auto &y: mx[x]){
				auto it = used.lb({y.S,0});
				if(it!=used.end() && (*it).F == y.S){
					pi fnd = *it;
					if(y.F+1 > fnd.S){
						used.erase(it);
						used.ins({fnd.F, y.F+1});
						swap(fnd.F,fnd.S);
						mx[i].erase(mx[i].find(fnd));
						mx[i].ins({y.F+1, y.S});
					}
				}else {
					mx[i].ins({y.F+1, y.S});
					used.ins({y.S, y.F+1});
					if(sz(mx[i])>block){
						pi rip = *mx[i].begin();
						mx[i].erase(mx[i].begin());
						used.erase(used.find({rip.S,rip.F}));
					}
				}
			}
		}
	}
	
	while(q--){
		int t,y; cin >> t>>y; 
		t--; 
		si notal; for(int i=0; i<y; i++){int x; cin >> x; notal.ins(x-1);}
		if(y>=block){
			vi dp(n,-INF);
			for(int i=0; i<n; i++)if(!notal.count(i)){
				dp[i]=0;
				for(auto &x: adj[i]){
					dp[i] = max(dp[x]+1, dp[i]);
				}
			}
			cout << (dp[t]<0? -1 : dp[t])<<endl;
		}else{
			int ans = -1;
			for(auto &x: mx[t])if(!notal.count(x.S)) ans = x.F;
			cout<<ans<<endl;
		}
	}
}

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