Submission #236163

#	Time	Username	Problem	Language	Result	Execution time	Memory
236163		MvC	Bitaro’s Party (JOI18_bitaro)	C++11	100 / 100	1065 ms	112940 KiB

bitaro

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const ll mod=1e9+7;
const int c=100;
using namespace std;
int n,m,q,x,y,i,j,nr,f[nmax],d[nmax],v[nmax],id[nmax],a[nmax],t;
vector<pair<int,int> >vc[nmax];
vector<int>g[nmax],cl;
pair<int,int>mx;
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	while(m--)
	{
		cin>>x>>y;
		g[y].pb(x);
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<(int)g[i].size();j++)
		{
			x=g[i][j];
			f[i]=max(f[i],f[x]+1);
		}
		d[i]=f[i];
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<(int)g[i].size();j++)id[g[i][j]]=0;
		nr=(int)g[i].size();
		for(t=0;t<c;t++)
		{
			mx=mkp(0,0);
			for(j=0;j<(int)g[i].size();j++)
			{
				x=g[i][j];
				if(id[x]==(int)vc[x].size())continue;
				while(id[x]<(int)vc[x].size() && v[vc[x][id[x]].sc])id[x]++;
				if(id[x]<(int)vc[x].size())mx=max(mx,vc[x][id[x]]);
				else nr--;
			}
			if(mx.sc)
			{
				vc[i].pb(mkp(mx.fr+1,mx.sc));
				v[mx.sc]=1;
				cl.pb(mx.sc);
			}
			else break;
			//if(!nr)break;
		}
		if((int)vc[i].size()<c)vc[i].pb(mkp(0,i));
		for(j=0;j<(int)cl.size();j++)v[cl[j]]=0;
		cl.clear();
	}
	while(q--)
	{
		cin>>x>>nr;
		for(i=1;i<=nr;i++)
		{
			cin>>a[i];
			v[a[i]]=1;
		}
		if(nr>=c)
		{
			for(i=a[1];i<=x;i++)
			{
				if(v[i])d[i]=-1;
				else d[i]=0;
				for(j=0;j<(int)g[i].size();j++)
				{
					y=g[i][j];
					if(d[y]==-1)continue;
					d[i]=max(d[i],d[y]+1);
				}
			}
			cout<<d[x]<<'\n';
			for(i=a[1];i<=x;i++)d[i]=f[i];
		}
		else
		{
			mx=mkp(-1,-1);
			for(i=0;i<(int)vc[x].size();i++)
			{
				if(!v[vc[x][i].sc])
				{
					mx=vc[x][i];
					break;
				}
			}
			cout<<mx.fr<<'\n';
		}
		for(i=1;i<=nr;i++)v[a[i]]=0;
	}
	return 0;
}

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