Submission #95054

#	Time	Username	Problem	Language	Result	Execution time	Memory
95054		ckodser	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1866 ms	306508 KiB

bitaro

#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=1e5+500;
const ll maxm=2e5+500;
const ll inf =1e9+900;
const ll mod=1e9+7;
const ll rad=330;

vector<ll> out[maxn];
vector<ll>  in[maxn];
vector<pii> maxx[maxn];

ll tmp[maxn];
bool hazf[maxn];

ll dp[maxn];
ll find_ans(ll t){
	dp[t]=0;
	ll ans=-1;
	if(!hazf[t])ans=0;
	for(ll i=t-1;i>=1;i--){
		dp[i]=-inf;
		for(auto v:out[i]){
			if(v<=t){
				dp[i]=max(dp[i],dp[v]+1);
			}
		}
		if(!hazf[i]){
			ans=max(ans,dp[i]);
		}
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	ll n,m,q;
	cin>>n>>m>>q;
	for(ll i=0;i<m;i++){
		ll s,e;
		cin>>s>>e;
		out[s].pb(e);
		in[e].pb(s);
	}
	for(ll i=1;i<=n;i++){
		vector<pii> vec;
		ll azz=0;
		for(auto v:in[i]){
			for(auto e:maxx[v]){
				azz+=(tmp[e.S]==0);
				tmp[e.S]=max(tmp[e.S],e.F+1);
			}
		}	
		maxx[i].reserve(azz+2);
		for(auto v:in[i]){
			for(auto e:maxx[v]){
				if(tmp[e.S]!=0){
					maxx[i].pb(mp(tmp[e.S],e.S));
					tmp[e.S]=0;
				}
			}
		}	
		maxx[i].pb(mp(0,i));

		sort(maxx[i].begin(),maxx[i].end());
		reverse(maxx[i].begin(),maxx[i].end());
		if(maxx[i].size()>rad)maxx[i].resize(rad);
	//	cout<<i<<":::"<<endl;
		for(auto e:maxx[i]){
	//		cout<<e.S<<' '<<e.F<<endl;
		}
	}
	for(ll qw=0;qw<q;qw++){
		ll t,y;
		cin>>t>>y;
		vector<ll> vec;
		for(ll i=0;i<y;i++){
			ll v;
			cin>>v;
			vec.pb(v);
			hazf[v]=1;
		}
		if(y<rad){
			bool cou=0;
			for(auto e:maxx[t]){
				if(!hazf[e.S]){
					cou=1;
					cout<<e.F<<endl;
					break;
				}
			}
			if(!cou){
				cout<<-1<<endl;
			}
		}else{
			cout<<find_ans(t)<<endl;
		}
		for(auto v:vec){
			hazf[v]=0;
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:79:12: warning: variable 'e' set but not used [-Wunused-but-set-variable]
   for(auto e:maxx[i]){
            ^

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