oj.uz

Submission #477686

# Submission time Handle Problem Language Result Execution time Memory
477686 2021-10-03T04:48:49 Z lory1608 Bitaro’s Party (JOI18_bitaro) C++17
7 / 100
 2000 ms 14668 KB 
#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=210,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-06.out","w",stdout);
	input();
	solve();
	return 0;
}

Compilation message

bitaro.cpp:10: warning: "gc" redefined
   10 | #define gc (_p1==_p2&&(_p2=(_p1=_buf)+fread(_buf,1,100000,stdin),_p1==_p2)?EOF:*_p1++)
      | 
bitaro.cpp:8: note: this is the location of the previous definition
    8 | #define gc getchar()
      |

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Correct 7 ms 11212 KB Output is correct
3 Correct 6 ms 11212 KB Output is correct
4 Correct 7 ms 11212 KB Output is correct
5 Correct 12 ms 11932 KB Output is correct
6 Correct 12 ms 11932 KB Output is correct
7 Correct 12 ms 11852 KB Output is correct
8 Correct 26 ms 13248 KB Output is correct
9 Correct 27 ms 13372 KB Output is correct
10 Correct 26 ms 13388 KB Output is correct
11 Correct 27 ms 13196 KB Output is correct
12 Correct 20 ms 12620 KB Output is correct
13 Correct 27 ms 13100 KB Output is correct
14 Correct 21 ms 12520 KB Output is correct
15 Correct 19 ms 12108 KB Output is correct
16 Correct 19 ms 12492 KB Output is correct
17 Correct 21 ms 12748 KB Output is correct
18 Correct 20 ms 12356 KB Output is correct
19 Correct 24 ms 12816 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Correct 7 ms 11212 KB Output is correct
3 Correct 6 ms 11212 KB Output is correct
4 Correct 7 ms 11212 KB Output is correct
5 Correct 12 ms 11932 KB Output is correct
6 Correct 12 ms 11932 KB Output is correct
7 Correct 12 ms 11852 KB Output is correct
8 Correct 26 ms 13248 KB Output is correct
9 Correct 27 ms 13372 KB Output is correct
10 Correct 26 ms 13388 KB Output is correct
11 Correct 27 ms 13196 KB Output is correct
12 Correct 20 ms 12620 KB Output is correct
13 Correct 27 ms 13100 KB Output is correct
14 Correct 21 ms 12520 KB Output is correct
15 Correct 19 ms 12108 KB Output is correct
16 Correct 19 ms 12492 KB Output is correct
17 Correct 21 ms 12748 KB Output is correct
18 Correct 20 ms 12356 KB Output is correct
19 Correct 24 ms 12816 KB Output is correct
20 Execution timed out 2081 ms 14668 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Correct 7 ms 11212 KB Output is correct
3 Correct 6 ms 11212 KB Output is correct
4 Correct 7 ms 11212 KB Output is correct
5 Correct 12 ms 11932 KB Output is correct
6 Correct 12 ms 11932 KB Output is correct
7 Correct 12 ms 11852 KB Output is correct
8 Correct 26 ms 13248 KB Output is correct
9 Correct 27 ms 13372 KB Output is correct
10 Correct 26 ms 13388 KB Output is correct
11 Correct 27 ms 13196 KB Output is correct
12 Correct 20 ms 12620 KB Output is correct
13 Correct 27 ms 13100 KB Output is correct
14 Correct 21 ms 12520 KB Output is correct
15 Correct 19 ms 12108 KB Output is correct
16 Correct 19 ms 12492 KB Output is correct
17 Correct 21 ms 12748 KB Output is correct
18 Correct 20 ms 12356 KB Output is correct
19 Correct 24 ms 12816 KB Output is correct
20 Execution timed out 2081 ms 14668 KB Time limit exceeded
21 Halted 0 ms 0 KB -