Submission #1190292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190292		boclobanchat	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	1468 ms	260664 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int MAXN=1e5+5;
const int sqr=320;
vector<ii> vi[MAXN];
vector<int> ds[MAXN];
int dp[MAXN];
bool ck[MAXN];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    while(m--)
    {
    	int l,r;
    	cin>>l>>r;
    	ds[r].push_back(l);
	}
	for(int i=1;i<=n;i++)
	{
		vi[i].push_back({0,i});
		for(auto v:ds[i])
		{
			vector<ii> curr,a=vi[i],b;
			for(auto u:vi[v]) b.push_back({u.fi+1,u.se});
			int l=0,r=0,sza=a.size(),szb=b.size();
			for(int j=0;j<sqr&&(l<sza||r<szb);j++)
			{
				ii x={-1,-1},y={-1,-1};
				while(l<sza&&ck[a[l].se]) l++;
				while(r<szb&&ck[b[r].se]) r++;
				if(l<sza) x=a[l];
				if(r<szb) y=b[r];
				if(x>y) l++,curr.push_back(x),ck[x.se]=true;
				else r++,curr.push_back(y),ck[y.se]=true;
			}
			for(auto v:curr) ck[v.se]=false;
			vi[i]=curr;
		}
	}
	while(q--)
	{
		int t,y;
		cin>>t>>y;
		if(y<sqr)
		{
			vector<int> vv;
			bool e=false;
			for(int i=1;i<=y;i++)
			{
				int res;
				cin>>res;
				ck[res]=true,vv.push_back(res);
			}
			for(auto v:vi[t]) if(!ck[v.se])
			{
				cout<<v.fi<<"\n";
				e=true;
				break;
			}
			if(!e) cout<<"-1\n";
			for(auto v:vv) ck[v]=false;
		}
		else
		{
			for(int i=1;i<=n;i++) dp[i]=0;
			for(int i=1;i<=y;i++)
			{
				int res;
				cin>>res;
				dp[res]=-1e9;
			}
			for(int i=1;i<=n;i++) for(auto v:ds[i]) dp[i]=max(dp[i],dp[v]+1);
			if(dp[t]<0) cout<<"-1\n";
			else cout<<dp[t]<<"\n";
		}
	}
}

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