QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#406298 | #8593. Coin | xiaolang | 0 | 12ms | 60656kb | C++14 | 874b | 2024-05-07 09:17:49 | 2024-05-07 09:18:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
vector<int>ed[N];
int in[N],tin[N];
int t1[N],t2[N],len1,len2;
int q[N];
int n,m;
void toposort(bool typ){
int l=1,r=0;
for(int i=1;i<=n;i++){
int u=((!typ)?i:n+1-i);
if(!tin[u])q[++r]=u;
}
while(l<=r){
int u=q[l++];
if(!typ)t1[++len1]=u;
else t2[++len2]=u;
int len=ed[u].size();
for(int i=0;i<len;i++){
int v=ed[u][((!typ)?i:len-1-i)];
tin[v]--;
if(!tin[v])q[++r]=v;
}
}
}
int ans[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
ed[u].push_back(v);
in[v]++;
}
for(int i=1;i<=n;i++)tin[i]=in[i];
toposort(0);
for(int i=1;i<=n;i++)tin[i]=in[i];
toposort(1);
for(int i=1;i<=n;i++)if(t1[i]==t2[i])ans[t1[i]]=2;
for(int i=1;i<=n;i++)cout<<ans[i]-1<<" ";
cout<<"\n";
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Acceptable Answer
time: 4ms
memory: 59048kb
input:
4 4 2 4 3 1 4 1 2 3
output:
1 1 -1 -1
result:
points 0.50 -1 correct
Test #2:
score: 3
Acceptable Answer
time: 12ms
memory: 60656kb
input:
6 8 1 5 5 4 6 2 2 5 4 3 6 1 6 5 2 1
output:
1 1 1 1 1 1
result:
points 0.50 -1 correct
Test #3:
score: 6
Accepted
time: 6ms
memory: 60064kb
input:
2 1 1 2
output:
1 1
result:
ok ac
Test #4:
score: 0
Wrong Answer
time: 7ms
memory: 59132kb
input:
6 12 1 5 5 4 6 2 2 5 4 3 6 5 1 5 1 5 2 4 6 3 1 3 4 3
output:
-1 1 1 1 1 -1
result:
wrong answer wa
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%