QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#252060#6526. CanvasC1942huangjiaxuWA 11ms27128kbC++142.5kb2023-11-15 15:17:302023-11-15 15:17:31

Judging History

你现在查看的是最新测评结果

  • [2023-11-15 15:17:31]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:27128kb
  • [2023-11-15 15:17:30]
  • 提交

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);
	if(T==1995)printf("%d %d\n",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);
		if(T==1995)printf("%d %d %d %d\n",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;
	}
	if(T>1000)return;
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 27128kb

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: 3ms
memory: 27108kb

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: 27092kb

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: 27124kb

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: 27128kb

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: 27048kb

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: 11ms
memory: 27088kb

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:

15 19
5 2 12 1
3 1 6 2
1 1 5 2
6 2 11 1
5 1 11 2
4 1 10 1
3 1 6 2
6 1 13 2
4 1 12 2
3 1 8 2
1 2 15 1
4 2 12 1
1 1 3 2
8 1 15 2
10 2 11 2
4 1 8 2
5 2 13 1
5 2 12 1
1 2 4 1
22
3 4 12 13 17 1 2 18 8 11 9 7 16 10 6 15 5 14
19
8 6 4 16 3 5 12 13 14 7 10 9 15 18 1 11 17 2
20
16 3 7 12 14 8 9 13 2 11 6 1 1...

result:

wrong answer Integer parameter [name=p_i] equals to 19, violates the range [1, 16] (test case 1)