QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#858759 | #9677. 基础博弈练习题 | zhouhuanyi | 0 | 266ms | 198480kb | C++14 | 3.6kb | 2025-01-16 22:13:23 | 2025-01-16 22:13:24 |
Judging History
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%