Submission #477685

#	Time	Username	Problem	Language	Result	Execution time	Memory
477685		lory1608	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2072 ms	14648 KiB

bitaro

//#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
#define ll long long
#define pb push_back
#define sz(x) (int)(x.size())
#define gc getchar()
#define mk make_pair
//#define gc (_p1==_p2&&(_p2=(_p1=_buf)+fread(_buf,1,100000,stdin),_p1==_p2)?EOF:*_p1++)
using namespace std;
char _buf[100000],*_p1=_buf,*_p2=_buf;
inline int gi()
{
	int x=0,f=1;
	char ch=gc;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=gc;
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=gc;
	}
	return (f==1)?x:-x;
}
const int maxn=2e5+5,B=150,inf=1e9;
priority_queue<pair<int,int>>pq[maxn];
int ind[maxn],tmp[maxn],c[maxn];
vector<int>e[maxn];
int dp[maxn],n,m,Q,t,y;
inline void input()
{
	n=gi(),m=gi(),Q=gi();
	FOR(i,1,m)
	{
		int u=gi(),v=gi();
		e[u].pb(v);tmp[v]++;
	}
}
bool vis[maxn];
int q[maxn],hd,tl;
inline void count()
{
	FOR(i,1,n)ind[i]=tmp[i],dp[i]=-inf;
	hd=0,tl=-1;
	FOR(i,1,n)if(!ind[i])q[++tl]=i;
	FOR(i,1,n)if(!vis[i])dp[i]=0;
	while(hd<=tl)
	{
		int u=q[hd++];
		for(int v:e[u])
		{
			dp[v]=max(dp[u]+1,dp[v]);
			ind[v]--;
			if(ind[v]==0)q[++tl]=v;
		}
	}
	printf("%d\n",dp[t]<0?-1:dp[t]);
}
inline void count2()
{
	priority_queue<pair<int,int>>pq=::pq[t];
	while(!pq.empty())
	{
		auto [w,id]=pq.top();
		pq.pop();
		if(vis[id])continue;
		else {return printf("%d\n",w),void();}
	}
	puts("-1");
}
bool bk[maxn];
inline auto merge(int x,int y)
{
	priority_queue<pair<int,int>>q,q1=pq[x],q2=pq[y];
	vector<int>temp;
	while(sz(temp)<=B)
	{
		if(q1.empty()&&q2.empty())break;
		pair<int,int>v;
		if(q1.empty())v=q2.top(),v.first++,q2.pop();
		else if(q2.empty())v=q1.top(),q1.pop();
		else if(q1.top().first>q2.top().first)v=q1.top(),q1.pop();
		else v=q2.top(),q2.pop(),v.first++;
		if(!bk[v.second])q.push(v),bk[v.second]=1,temp.pb(v.second);
	}
	for(int x:temp)bk[x]=0;
	return q;
}
inline void solve()
{
	queue<int>q;
	FOR(i,1,n)ind[i]=tmp[i],pq[i].push({0,i});
	FOR(i,1,n)if(!ind[i])q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		for(int v:e[u])
		{
			pq[v]=merge(v,u),ind[v]--;
			if(ind[v]==0)q.push(v);
		}
	}
	FOR(i,1,Q)
	{
		t=gi(),y=gi();
		FOR(j,1,y)c[j]=gi();
		FOR(j,1,y)vis[c[j]]=1;
		if(y>=B)count();
		else count2();
		FOR(j,1,y)vis[c[j]]=0;
	}
}
int main()
{
	//freopen("03-06.in","r",stdin);
	//freopen("03-03.out","w",stdout);
	input();
	solve();
	return 0;
}

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