QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#252057 | #6526. Canvas | C1942huangjiaxu | WA | 12ms | 27164kb | C++14 | 2.4kb | 2023-11-15 15:15:10 | 2023-11-15 15:15:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int T,n,m,p[N],v1[N],bg,ed,ans,dfn[N],low[N],st[N],tp,co[N],col,id[N];
bool c1[N],c2[N],v2[N],us[N],vis[N];
queue<int>q;
vector<int>e[N],g[N];
struct node{
int l,x,r,y;
}a[N];
void add(int x){
if(!c2[x]){
c2[x]=true;
q.push(x);
}
}
void dfs(int x){
while(!g[x].empty()){
int u=g[x].back();
g[x].pop_back();
int y=a[u].l^a[u].r^x;
p[ed--]=u;
dfs(y);
c2[y]=true,c2[x]=false;
}
}
void tarjan(int x){
dfn[x]=low[x]=++dfn[0],vis[x]=true,st[++tp]=x;
for(auto v:g[x]){
int u=a[v].l^a[v].r^x;
if(!dfn[u]){
tarjan(u);
low[x]=min(low[x],low[u]);
}else if(vis[u])low[x]=min(low[x],dfn[u]);
}
if(dfn[x]==low[x]){
co[x]=++col;
while(st[tp]!=x){
co[st[tp]]=col;
vis[st[tp]]=false;
--tp;
}
vis[x]=false,--tp;
}
}
bool cmp(int x,int y){
return co[x]>co[y];
}
void solve(){
scanf("%d%d",&n,&m);
bg=1,ed=m,dfn[0]=col=ans=0;
for(int i=1;i<=n;++i)c1[i]=c2[i]=v1[i]=v2[i]=0,e[i].clear();
for(int i=1,l,x,r,y;i<=m;++i){
scanf("%d%d%d%d",&l,&x,&r,&y);
us[i]=false;
a[i]=node{l,x,r,y};
c1[l]=c1[r]=true;
if(x==1&&y==1){
us[i]=true;
p[bg++]=i;
continue;
}
if(x==2&&y==2){
us[i]=true;
p[ed--]=i;
add(l),add(r);
continue;
}
if(x==2)v2[l]=true;
else ++v1[l];
if(y==2)v2[r]=true;
else ++v1[r];
e[l].push_back(i);
e[r].push_back(i);
}
for(int i=1;i<=n;++i)if(v2[i]&&!v1[i])add(i);
for(int i=1;i<=m;++i)if(!us[i]){
if(a[i].x==1&&!v2[a[i].l]){
us[i]=true;
p[ed--]=i;
add(a[i].r);
}
if(a[i].y==1&&!v2[a[i].r]){
us[i]=true;
p[ed--]=i;
add(a[i].l);
}
}
while(!q.empty()){
int x=q.front();
q.pop();
for(auto v:e[x])if(!us[v]){
int y=x^a[v].l^a[v].r;
us[v]=true;
if((a[v].l==x)^(a[v].x>1)){
add(y);
p[ed--]=v;
}else{
p[bg++]=v;
--v1[y];
if(!v1[y])add(y);
}
}
}
for(int i=1;i<=m;++i)if(!us[i]){
if(a[i].x==2)g[a[i].r].push_back(i);
else g[a[i].l].push_back(i);
}
for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;++i)id[i]=i;
sort(id+1,id+n+1,cmp);
for(int i=1;i<=n;++i)dfs(id[i]);
for(int i=1;i<=n;++i){
if(c1[i])++ans;
if(c2[i])++ans;
}
printf("%d\n",ans);
for(int i=1;i<=m;++i)printf("%d%c",p[i]," \n"[i==m]);
}
int main(){
scanf("%d",&T);
while(T--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 27104kb
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: 27132kb
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 10 5 4 7 3 2 1 6 11 9 12
result:
ok Correct. (1 test case)
Test #3:
score: 0
Accepted
time: 3ms
memory: 27096kb
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: 3ms
memory: 27160kb
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 1 3 2 6 5
result:
ok Correct. (1 test case)
Test #5:
score: 0
Accepted
time: 7ms
memory: 27104kb
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:
7 3 4 1 5 2
result:
ok Correct. (1 test case)
Test #6:
score: 0
Accepted
time: 3ms
memory: 27160kb
input:
1 7 6 1 2 5 1 2 1 7 2 1 2 7 1 2 2 7 1 1 1 5 2 1 2 3 1
output:
8 1 3 4 2 5 6
result:
ok Correct. (1 test case)
Test #7:
score: -100
Wrong Answer
time: 12ms
memory: 27164kb
input:
2000 15 16 2 2 3 1 12 2 15 1 3 2 9 1 6 2 14 1 2 1 15 2 5 2 6 1 7 1 10 1 9 2 15 1 2 2 3 1 4 2 12 1 2 2 9 1 5 2 8 2 3 2 13 1 12 1 13 2 9 2 13 1 5 1 14 2 15 15 5 2 11 1 1 2 8 1 8 1 15 2 6 2 8 2 8 2 9 1 1 1 6 2 6 1 9 2 2 2 5 1 2 1 10 2 7 2 10 1 1 1 15 2 5 2 15 1 7 1 11 2 1 1 2 1 5 2 9 1 15 14 3 1 5 2 1 ...
output:
23 7 6 10 4 13 15 14 2 1 9 3 11 8 5 16 12 20 14 6 5 1 13 10 9 8 12 11 15 3 2 7 4 21 2 14 8 11 13 6 10 3 9 12 4 7 1 5 18 7 13 12 4 1 5 11 6 8 10 14 9 3 2 21 6 5 2 7 1 3 17 18 12 9 16 19 10 13 11 14 8 4 15 21 3 11 9 7 13 14 6 2 8 5 4 12 10 1 21 3 7 15 8 6 11 9 13 1 4 5 12 14 2 10 19 11 7 9 16 13 15 17...
result:
wrong answer Participant's solution is incorrect. (test case 5)