Submission #111743

#	Time	Username	Problem	Language	Result	Execution time	Memory
111743		zscoder	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1989 ms	217476 KiB

bitaro

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
 
const int C = 250;
 
vi adj[111111];
vi radj[111111];
vector<ii> dp[111111];
int n,m,q; 
bool isbad[111111];
 
void solve_large(int u)
{
	int ans = -1;
	vi innerdp(n+1,-1);
	innerdp[u] = 0;
	for(int i=u;i>=0;i--)
	{
		for(int v:adj[i])
		{
			if(innerdp[v]!=-1) innerdp[i] = max(innerdp[i], innerdp[v] + 1);
		}
		if(!isbad[i]) ans = max(ans, innerdp[i]);
	}
	cout<<ans<<'\n';
}
 
bool appeared[111111];
vector<ii> mergevector(vector<ii> &v1, vector<ii> &v2)
{
	vector<ii> V; vi A;
	int p1 = 0; int p2 = 0;
	while((p1<v1.size()||p2<v2.size())&&V.size()<C+1)
	{
		int val1 = -100000; int val2 = -100000;
		if(p1<v1.size()) val1 = v1[p1].fi;
		if(p2<v2.size()) val2 = v2[p2].fi+1;
		if(val1>val2)
		{
			V.pb(mp(val1, v1[p1].se));
			appeared[v1[p1].se]=1;A.pb(v1[p1].se);
			p1++;
		}
		else
		{
			V.pb(mp(val2, v2[p2].se));
			appeared[v2[p2].se]=1;A.pb(v2[p2].se);
			p2++;
		}
		while(p1<v1.size()&&appeared[v1[p1].se]) p1++;
		while(p2<v2.size()&&appeared[v2[p2].se]) p2++;
	}
	for(int x:A) appeared[x]=0;
	return V;
}
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>q;
	for(int i=0;i<m;i++)
	{
		int u, v; cin>>u>>v;u--;v--;
		adj[u].pb(v); radj[v].pb(u);
	}
	for(int i=0;i<n;i++)
	{
		dp[i].pb(mp(0,i));
		for(int v:radj[i])
		{
			dp[i] = mergevector(dp[i], dp[v]);
		}
		/*
		cerr<<"DP "<<i<<'\n';
		for(ii x:dp[i])
		{
			cerr<<x.fi<<' '<<x.se<<'\n';
		}
		*/
	}
	for(int i=0;i<q;i++)
	{
		int u; cin>>u; u--;
		int k; cin>>k; vi vec;
		for(int j=0;j<k;j++)
		{
			int v; cin>>v; v--; vec.pb(v);
		}
		for(int v:vec) isbad[v]=1;
		if(k>=C-1)
		{
			solve_large(u);
		}
		else
		{
			int ans = -1;
			for(ii x:dp[u])
			{
				if(isbad[x.se]) continue;
				ans = max(ans, x.fi);
			}
			cout<<ans<<'\n';
		}
		for(int v:vec) isbad[v]=0;
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > mergevector(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
bitaro.cpp:52:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((p1<v1.size()||p2<v2.size())&&V.size()<C+1)
         ~~^~~~~~~~~~
bitaro.cpp:52:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while((p1<v1.size()||p2<v2.size())&&V.size()<C+1)
                       ~~^~~~~~~~~~
bitaro.cpp:55:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p1<v1.size()) val1 = v1[p1].fi;
      ~~^~~~~~~~~~
bitaro.cpp:56:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p2<v2.size()) val2 = v2[p2].fi+1;
      ~~^~~~~~~~~~
bitaro.cpp:69:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1<v1.size()&&appeared[v1[p1].se]) p1++;
         ~~^~~~~~~~~~
bitaro.cpp:70:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p2<v2.size()&&appeared[v2[p2].se]) p2++;
         ~~^~~~~~~~~~

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