QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #406309 | #8593. Coin | xiaolang | 3 | 12ms | 60800kb | C++14 | 1020b | 2024-05-07 09:28:57 | 2024-05-07 09:29:15 |
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;
map<pair<int,int>,int>mp;
void toposort(bool typ){
int len=0;
for(int i=1;i<=n;i++){
int u=((!typ)?i:n+1-i);
if(!tin[u])q[++len]=u;
}
while(len>0){
int u=q[len--];
//cout<<u<<" ";
if(!typ)t1[++len1]=u;
else t2[++len2]=u;
int lenn=ed[u].size();
for(int i=0;i<lenn;i++){
int v=ed[u][((!typ)?i:lenn-1-i)];
tin[v]--;
if(!tin[v])q[++len]=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);
if(mp[make_pair(u,v)])continue;
mp[make_pair(u,v)]=1;
ed[u].push_back(v);
in[v]++;
}
for(int i=1;i<=n;i++)tin[i]=in[i];
toposort(0);
//cout<<"\n";
for(int i=1;i<=n;i++)tin[i]=in[i];
toposort(1);
// cout<<"\n";
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: 3
Acceptable Answer
Test #1:
score: 3
Acceptable Answer
time: 0ms
memory: 60480kb
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: 8ms
memory: 59728kb
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: 12ms
memory: 60204kb
input:
2 1 1 2
output:
1 1
result:
ok ac
Test #4:
score: 3
Acceptable Answer
time: 8ms
memory: 60612kb
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:
points 0.50 -1 correct
Test #5:
score: 3
Acceptable Answer
time: 8ms
memory: 59624kb
input:
7 20 1 6 6 3 1 4 1 5 1 7 1 2 1 5 2 3 4 5 7 2 2 4 5 3 6 3 1 3 4 3 7 5 2 6 4 6 7 2 7 5
output:
1 1 1 1 -1 -1 1
result:
points 0.50 -1 correct
Test #6:
score: 3
Acceptable Answer
time: 3ms
memory: 59756kb
input:
7 20 5 6 1 3 3 6 4 1 7 4 2 5 4 3 2 6 7 5 4 6 2 6 2 1 4 5 1 3 1 5 7 1 7 6 4 1 7 6 3 6
output:
1 -1 -1 -1 -1 1 -1
result:
points 0.50 -1 correct
Test #7:
score: 3
Acceptable Answer
time: 4ms
memory: 59192kb
input:
7 20 7 6 4 5 6 4 3 6 4 1 6 2 3 5 5 2 7 6 1 2 3 6 6 4 7 1 6 1 7 1 4 5 3 6 3 5 4 5 3 1
output:
-1 1 -1 1 -1 1 -1
result:
points 0.50 -1 correct
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
50%
Acceptable Answer
Test #8:
score: 0
Wrong Answer
time: 3ms
memory: 60800kb
input:
20 100 5 20 4 5 18 16 1 13 14 9 11 19 6 4 7 20 16 11 8 13 4 5 16 9 12 14 7 12 11 3 9 11 9 11 13 6 3 10 12 9 13 4 20 12 13 6 18 11 5 7 5 7 15 18 12 15 17 13 15 18 3 2 11 2 11 2 15 19 4 19 14 19 14 9 17 3 1 18 8 10 16 19 1 6 7 2 5 12 1 18 8 20 5 18 8 5 4 16 1 15 5 19 18 19 17 10 1 10 17 3 10 2 3 10 17...
output:
-1 -1 -1 1 1 1 1 1 1 -1 1 1 1 -1 1 -1 -1 -1 -1 1
result:
wrong answer wa
Subtask #3:
score: 0
Skipped
Dependency #1:
50%
Acceptable Answer
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
50%
Acceptable Answer
Dependency #2:
0%