Submission #697491

#	Time	Username	Problem	Language	Result	Execution time	Memory
697491		myrcella	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	1118 ms	333980 KiB

bitaro

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 2e5+10;

int sz = 400;
int n,m,q;
vector <int> edge[maxn];
vector <pii> mx[maxn];
bool bad[maxn];
bool have[maxn];
vector <pii> tmp;
int dp[maxn];

int getdp(int pos) {
	if (dp[pos]!=-1) return dp[pos];
	dp[pos] = -mod;
	if (!bad[pos]) dp[pos] = 0;
	for (int v:edge[pos]) dp[pos] = max(dp[pos],getdp(v)+1);
	return dp[pos];
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m>>q;
	rep(i,0,m) {
		int u,v;cin>>u>>v;
		edge[v].pb(u);
	}
	rep(i,1,n+1) {
		mx[i].pb({0,i});
		for (int v:edge[i]) {
			int cur = 0, cur1 = 0;
			while (cur<SZ(mx[i]) and cur1<SZ(mx[v]) and SZ(tmp)<=sz) {
				if (mx[i][cur].fi>mx[v][cur1].fi + 1) {
					if (!have[mx[i][cur].se]) tmp.pb(mx[i][cur]),have[tmp.back().se]=true;
					cur++;
				}
				else {
					if (!have[mx[v][cur1].se]) tmp.pb(MP(mx[v][cur1].fi+1,mx[v][cur1].se)),have[tmp.back().se];
					cur1++;
				}
			}
			while (cur<SZ(mx[i]) and SZ(tmp)<=sz) {
					if (!have[mx[i][cur].se]) tmp.pb(mx[i][cur]),have[tmp.back().se]=true;
					cur++;
				}
			while (cur1<SZ(mx[v]) and SZ(tmp)<=sz) {
					if (!have[mx[v][cur1].se]) tmp.pb(MP(mx[v][cur1].fi+1,mx[v][cur1].se)),have[tmp.back().se];
					cur1++;
				}
			mx[i] = tmp;
			while(!tmp.empty()) have[tmp.back().se] = false, tmp.pop_back();
		}
	}
	while (q--) {
		vector <int> tmpp;
		int pos,e;cin>>pos>>e;
		rep(i,0,e) {
			int x;cin>>x;
			tmpp.pb(x);
			bad[x] = true;
		}
		if (e<sz) {
			int cur=0;
			while (cur<SZ(mx[pos]) and bad[mx[pos][cur].se]) cur++;
			if (cur<SZ(mx[pos])) cout<<mx[pos][cur].fi<<"\n";
			else cout<<"-1\n";
		}
		else {
			rep(i,1,pos+1) dp[i] = -1;
			int ans = getdp(pos);
			if (ans>=0)	cout<<getdp(pos)<<"\n";
			else cout<<"-1\n";
		}
		while (!tmpp.empty()) bad[tmpp.back()] = false,tmpp.pop_back();
	}
	return 0;
}

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