QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#858759#9677. 基础博弈练习题zhouhuanyi0 266ms198480kbC++143.6kb2025-01-16 22:13:232025-01-16 22:13:24

Judging History

This is the latest submission verdict.

  • [2025-01-16 22:13:24]
  • Judged
  • Verdict: 0
  • Time: 266ms
  • Memory: 198480kb
  • [2025-01-16 22:13:23]
  • Submitted

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#define N 1000000
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,type;
	bool operator < (const reads &t)const
	{
		return num!=t.num?num<t.num:type<t.type;
	}
};
reads w[N+1];
struct rds
{
	int num,data;
	bool operator < (const rds &t)const
	{
		return num<t.num;
	}
};
set<rds>s;
int n,m,k,leng,ps[N+1],belong[N+1],minn[N+1],in[N+1],cater,L[N+1],R[N+1],a[N+1],b[N+1],dfn[N+1],low[N+1],delta[N+1],stk[N+1],top,ans[N+1],dque[N+1],l=1,r;
bool used[N+1],vis[N+1];
vector<int>E[N+1];
vector<int>v[N+1];
vector<int>ES[N+1];
vector<int>st[N+1];
void tarjan(int x)
{
	dfn[x]=low[x]=++leng,used[x]=1,stk[++top]=x;
	for (int i=0;i<E[x].size();++i)
	{
		if (!dfn[E[x][i]]) tarjan(E[x][i]),low[x]=min(low[x],low[E[x][i]]);
		else if (used[E[x][i]]) low[x]=min(low[x],dfn[E[x][i]]);
	}
	if (dfn[x]==low[x])
	{
		++cater;
		while (stk[top]!=x) belong[stk[top]]=cater,v[cater].push_back(stk[top]),used[stk[top]]=0,top--;
		belong[stk[top]]=cater,v[cater].push_back(stk[top]),belong[stk[top]]=cater,used[stk[top]]=0,top--;
	}
	return;
}
int main()
{
	int top,x,y,res;
	n=read(),m=read(),k=read();
	for (int i=1;i<=n;++i) a[i]=read(),minn[i]=inf,w[i]=(reads){inf,0};
	for (int i=1;i<=k;++i) b[i]=read(),minn[b[i]]=min(minn[b[i]],i);
	for (int i=1;i<=n;++i) delta[i]=minn[a[i]];
	for (int i=1;i<=m;++i) x=read(),y=read(),E[x].push_back(y);
	for (int i=1;i<=n;++i)
		if (!dfn[i])
			tarjan(i);
	for (int i=1;i<=n;++i)
		for (int j=0;j<E[i].size();++j)
			if (belong[i]!=belong[E[i][j]])
				ES[belong[E[i][j]]].push_back(belong[i]),in[belong[i]]++;
	for (int i=1;i<=cater;++i)
		if (!in[i])
			dque[++r]=i;
	for (int i=1;i<=cater;++i)
	{
		res=inf;
		for (int j=0;j<v[i].size();++j) res=min(res,delta[v[i][j]]);
		L[i]=res;
		if (v[i].size()!=1&&res!=inf) st[res].push_back(i);
		else R[i]=res;
	}
	for (int i=k;i>=1;--i)
	{
		if (!ps[b[i]]) s.insert((rds){i,b[i]});
		else s.erase((rds){ps[b[i]],b[i]}),ps[b[i]]=i,s.insert((rds){i,b[i]});
		for (int j=0;j<st[i].size();++j)
		{
			for (int k=0;k<v[st[i][j]].size();++k) vis[a[v[st[i][j]][k]]]=1;
			res=k;
			for (auto it:s)
				if (!vis[it.data])
				{
					res=it.num-1;
					break;
				}
			R[st[i][j]]=res;
			for (int k=0;k<v[st[i][j]].size();++k) vis[a[v[st[i][j]][k]]]=0;
		}
	}
	while (l<=r)
	{
		top=dque[l++];
		if (w[top].num<=L[top])
		{
			for (int i=0;i<v[top].size();++i) ans[v[top][i]]=w[top].num+w[top].type-1;
		}
		else if (w[top].num==inf)
		{
			if (v[top].size()==1) ans[v[top][0]]=-1;
			else
			{
				for (int i=0;i<v[top].size();++i) ans[v[top][i]]=L[top]+((R[top]-L[top])&1)-1;
			}
		}
		else
		{
			if (v[top].size()==1) ans[v[top][0]]=w[top].num+w[top].type-1;
			else
			{
				if (w[top].num>R[top]+1)
				{
					for (int i=0;i<v[top].size();++i) ans[v[top][i]]=L[top]+((R[top]-L[top])&1)-1;
				}
				else
				{
					for (int i=0;i<v[top].size();++i) ans[v[top][i]]=L[top]+(((w[top].num-L[top])&1)^w[top].type)-1;
				}
			}
		}
		if (w[top].num>L[top])
		{
			if (w[top].num>R[top]+1) w[top]=(reads){L[top],(R[top]-L[top])&1};
			else w[top]=(reads){L[top],((w[top].num-L[top])&1)^w[top].type};
		}
		for (int i=0;i<ES[top].size();++i)
		{
			w[ES[top][i]]=min(w[ES[top][i]],w[top]),in[ES[top][i]]--;
			if (!in[ES[top][i]]) dque[++r]=ES[top][i];
		}
	}
	for (int i=1;i<=n;++i) printf("%d ",ans[i]);
	puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 13ms
memory: 120788kb

input:

83 93 13
8 9 10 7 7 7 6 3 1 10 6 2 5 7 1 3 4 2 1 10 7 4 8 9 2 2 1 9 2 5 1 7 8 6 1 9 9 10 4 1 2 9 2 3 4 2 9 10 8 1 4 1 8 4 1 4 4 7 4 8 2 9 2 5 2 2 3 3 8 5 2 9 3 10 8 8 1 6 6 1 6 7 10
7 5 10 3 2 2 7 4 8 7 6 6 5
56 36
33 41
32 62
37 7
6 53
41 13
9 36
44 77
38 62
76 16
72 5
40 13
55 60
5 78
72 45
13 44
...

output:

0 999999999 -1 -1 2 0 -1 7 0 -1 3 -1 0 0 1 -1 0 -1 0 0 -1 0 -1 2 -1 -1 999999999 999999999 -1 -1 0 0 0 -1 0 999999999 3 0 0 0 0 0 -1 -1 -1 -1 0 0 0 999999999 0 0 3 0 0 0 -1 -1 3 -1 0 0 0 0 0 8 -1 -1 1 -1 -1 0 3 4 -1 3 999999999 3 -1 0 0 0 -1 

result:

wrong answer 2nd numbers differ - expected: '-1', found: '999999999'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #6:

score: 30
Accepted
time: 53ms
memory: 141632kb

input:

100000 355071 10000
5 7 4 7 4 1 10 5 9 4 9 4 3 10 5 4 9 1 7 10 1 6 10 3 10 9 8 4 6 3 10 8 6 8 3 5 10 9 7 7 1 3 8 8 6 2 8 4 2 9 1 10 3 6 3 8 9 10 5 7 3 2 1 5 7 4 3 4 6 4 2 7 2 5 5 6 4 6 7 4 4 6 4 2 3 9 9 9 10 8 1 6 7 2 9 8 2 3 1 6 9 4 10 3 10 1 2 3 3 4 1 1 1 5 8 6 8 3 1 6 2 9 5 9 4 7 2 10 7 5 2 2 7 4...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 100000 numbers

Test #7:

score: 30
Accepted
time: 63ms
memory: 135752kb

input:

100000 300561 10000
6 3 6 10 10 9 7 3 6 4 5 4 1 2 3 2 10 6 3 7 8 7 10 5 9 10 2 3 9 5 6 10 9 1 4 9 1 10 7 2 9 10 5 5 9 3 5 5 5 9 9 5 1 7 5 10 8 6 8 4 5 9 2 10 1 6 4 10 10 9 2 1 10 1 9 5 3 2 9 3 4 8 10 7 5 2 4 5 3 6 9 7 5 10 2 7 4 7 10 8 1 7 7 1 7 7 6 6 7 1 5 4 6 2 1 8 6 10 6 10 1 5 8 4 6 2 10 6 10 4 ...

output:

0 4 0 0 3 0 0 4 0 0 0 0 0 0 0 0 0 0 1 0 0 1 7 0 1 2 0 0 0 0 4 0 0 1 0 0 0 2 0 0 0 3 0 0 1 0 0 0 3 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 9 0 0 0 2 0 3 1 0 2 1 0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 2 2 0 0 1 0 0 0 0 0 1 0 0 1 0 2 0 6 0 0 1 5 0 0 3 0 0 1 2 0 2 3 0 0 2 0 1 1 9 0 2 5 2 0 2 1 3 1 6 4 0 0 1 0 2 1 0 ...

result:

ok 100000 numbers

Test #8:

score: 0
Wrong Answer
time: 266ms
memory: 198480kb

input:

500000 1770902 50000
4 7 2 3 6 10 8 2 2 6 2 3 3 7 3 1 5 2 1 10 2 6 3 4 2 8 10 6 6 10 9 3 3 2 9 10 4 5 3 9 7 10 4 3 6 6 4 9 4 4 4 1 9 5 6 10 3 7 5 8 10 1 6 5 1 7 9 10 2 4 6 9 6 2 2 8 4 7 9 1 9 4 6 4 6 3 9 2 2 1 1 1 8 3 10 10 2 2 5 15 20 18 17 15 12 11 11 11 11 12 13 19 18 20 15 11 11 20 10 14 13 14 1...

output:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 4 1 1 1 4 1 10 1 1 1 4 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 -1 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1...

result:

wrong answer 500000th numbers differ - expected: '-1', found: '999999999'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%