QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#704821 | #6526. Canvas | lllei# | WA | 7ms | 33316kb | C++14 | 1.6kb | 2024-11-02 21:08:44 | 2024-11-02 21:08:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
vector<int>e[N],num[N];
bool vis[N],vis1[N];
int n,m;
int ans[N];
int s[N];
int d[N];
vector<int>ans2,ans3;
void dfs(int now)
{
//cout<<now<<endl;
ans[now]=2;
vis[now]=1;
int tmp=e[now].size();
for(int i=0;i<tmp;i++)
if(!vis[e[now][i]]){
ans2.push_back(num[now][i]);
dfs(e[now][i]);
}
else
ans3.push_back(num[now][i]);
return;
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
ans2.clear();ans3.clear();
for(int i=1;i<=n;i++){
vis[i]=0;vis1[i]=0;ans[i]=0;
s[i]=0;d[i]=0;
e[i].clear();
num[i].clear();
}
for(int i=1;i<=m;i++)
{
int l,x,r,y;
cin>>l>>x>>r>>y;
if(x>y) {
swap(l,r);
swap(x,y);
}
vis1[l]=vis1[r]=1;
if(x==2&&y==2)
{
ans[l]=ans[r]=2;
s[l]=1;s[r]=1;
ans2.push_back(i);
}
if(x==1&&y==2)
{
e[l].push_back(r);
num[l].push_back(i);
d[r]++;
}
if(x==1&&y==1)
ans3.push_back(i);
}
for(int i=1;i<=n;i++){
if(s[i]&&!vis[i]&&vis1[i])
dfs(i);
}
for(int i=1;i<=n;i++)
if(d[i]==0&&!vis[i]&&vis1[i])
{
dfs(i);
ans[i]=1;
}
for(int i=1;i<=n;i++)
if(!vis[i]&&vis1[i])
{
dfs(i);
ans[i]=1;
}
for(int i=1;i<=n;i++)
if(vis1[i])
ans[i]=max(ans[i],1);
int ans1=0;
for(int i=1;i<=n;i++)
{
ans1+=ans[i];
//cout<<ans[i]<<' ';
}
cout<<ans1<<endl;
int tmp=ans3.size();
for(int i=0;i<tmp;i++)cout<<ans3[i]<<' ';
tmp=ans2.size();
for(int i=tmp-1;i>=0;i--)cout<<ans2[i]<<' ';
cout<<endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 33048kb
input:
2 4 4 1 1 2 2 3 2 4 1 1 2 3 2 2 1 4 1 4 2 3 2 4 1 1 2 3 1
output:
7 4 2 1 3 5 2 1
result:
ok Correct. (2 test cases)
Test #2:
score: 0
Accepted
time: 0ms
memory: 32380kb
input:
1 10 13 1 1 2 2 2 1 3 2 1 2 3 1 3 1 4 2 4 1 5 2 5 1 6 2 4 2 6 1 7 1 8 2 8 1 9 2 7 2 9 1 5 2 9 1 8 2 10 2 1 1 10 1
output:
19 13 8 5 3 4 2 1 7 6 11 10 9 12
result:
ok Correct. (1 test case)
Test #3:
score: 0
Accepted
time: 0ms
memory: 31980kb
input:
1 7 5 2 1 6 2 1 2 6 1 1 1 5 1 2 2 7 1 1 1 7 2
output:
8 3 2 1 4 5
result:
ok Correct. (1 test case)
Test #4:
score: 0
Accepted
time: 7ms
memory: 33316kb
input:
1 7 6 2 1 7 2 2 1 4 2 1 2 4 1 2 1 6 1 1 1 6 2 2 2 6 1
output:
9 4 3 2 1 6 5
result:
ok Correct. (1 test case)
Test #5:
score: -100
Wrong Answer
time: 4ms
memory: 33076kb
input:
1 7 5 5 2 7 1 5 1 6 2 3 2 7 1 3 2 6 1 6 1 7 2
output:
6 4 1 3 5 2
result:
wrong answer Participant's solution is incorrect. (test case 1)