QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#302280	#4829. Mark on a Graph	Loging^#	AC ✓	3ms	5948kb	C++20	1.6kb	2024-01-10 18:27:34	2024-01-10 18:27:34

Judging History

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

[2024-01-10 18:27:34]
评测

测评结果：AC
用时：3ms
内存：5948kb

查看

[2024-01-10 18:27:34]
提交

answer

#include<cstdio>
#include<vector>
#include<bitset>
#define M 100005
using namespace std;
struct E{
	int to,nx;
}edge[M<<1];
int tot,head[M];
void Addedge(int a,int b){
	edge[++tot].to=b;
	edge[tot].nx=head[a];
	head[a]=tot;
}
bitset<1005>way[1005];
bool mark[M];
vector<int>S;
int Ans[10][2],sz;
int main(){
//	freopen("002.in","r",stdin);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)way[i].reset();
	while(m--){
		int a,b;
		scanf("%d%d",&a,&b);
		way[a].flip(b);
		way[b].flip(a);
	}
	int x=1,y=2;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)if(way[i][j]){
			Addedge(i,j);
			x=i;y=j;
		}
	}
	bool flag=false;
	for(int now=1;now<=n;now++){
		for(int i=head[now];i;i=edge[i].nx){
			for(int j=head[now];j;j=edge[j].nx){
				if(i==j)continue;
				for(int k=head[now];k;k=edge[k].nx){
					if(i==j||i==k)continue;
					if(!way[edge[j].to][edge[i].to]||!way[edge[j].to][edge[k].to])continue;
					if(!way[edge[i].to][edge[k].to])continue;
					flag=true;
					break;
				}
				if(flag)break;
			}
			if(flag)break;
		}
		if(flag)break;
	}
	if(flag)puts("ok");
	else{
		int cnt=2;
		S.push_back(x);
		S.push_back(y);
		mark[x]=mark[y]=true;
		for(int i=1;i<=n;i++){
			if(mark[i])continue;
			cnt++;
			mark[i]=true;
			S.push_back(i);
			if(cnt==4)break;
		}
		for(int i=0;i<(int)S.size();i++){
			for(int j=i+1;j<(int)S.size();j++){
				if(!way[S[i]][S[j]]){
					way[S[i]][S[j]]=way[S[j]][S[i]]=1;
					sz++;
					Ans[sz][0]=S[i];
					Ans[sz][1]=S[j];
				}
			}
		}
		puts("mark");
		printf("%d\n",sz);
		for(int i=1;i<=sz;i++)printf("%d %d\n",Ans[i][0],Ans[i][1]);
	}
	return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 5832kb

input:

output:

input:

output:

ok

result:

ok all right

Test #2:

score: 100

Accepted

time: 1ms

memory: 4048kb

input:

output:

input:

output:

ok

result:

ok all right

Test #3:

score: 100

Accepted

time: 3ms

memory: 4120kb

input:

output:

input:

output:

ok

result:

ok all right

Test #4:

score: 100

Accepted

time: 2ms

memory: 4076kb

input:

output:

input:

output:

ok

result:

ok all right

Test #5:

score: 100

Accepted

time: 2ms

memory: 5888kb

input:

output:

input:

output:

ok

result:

ok all right

Test #6:

score: 100

Accepted

time: 2ms

memory: 4080kb

input:

output:

input:

output:

ok

result:

ok all right

Test #7:

score: 100

Accepted

time: 2ms

memory: 4024kb

input:

output:

input:

output:

ok

result:

ok all right

Test #8:

score: 100

Accepted

time: 3ms

memory: 4084kb

input:

output:

input:

output:

ok

result:

ok all right

Test #9:

score: 100

Accepted

time: 3ms

memory: 4020kb

input:

output:

input:

output:

ok

result:

ok all right

Test #10:

score: 100

Accepted

time: 2ms

memory: 3988kb

input:

output:

input:

output:

ok

result:

ok all right

Test #11:

score: 100

Accepted

time: 2ms

memory: 4012kb

input:

output:

input:

output:

ok

result:

ok all right

Test #12:

score: 100

Accepted

time: 0ms

memory: 4016kb

input:

output:

input:

output:

ok

result:

ok all right

Test #13:

score: 100

Accepted

time: 1ms

memory: 4056kb

input:

output:

input:

output:

ok

result:

ok all right

Test #14:

score: 100

Accepted

time: 2ms

memory: 4020kb

input:

output:

input:

output:

ok

result:

ok all right

Test #15:

score: 100

Accepted

time: 2ms

memory: 3976kb

input:

output:

input:

output:

ok

result:

ok all right

Test #16:

score: 100

Accepted

time: 2ms

memory: 4072kb

input:

output:

input:

output:

ok

result:

ok all right

Test #17:

score: 100

Accepted

time: 2ms

memory: 4068kb

input:

output:

input:

output:

ok

result:

ok all right

Test #18:

score: 100

Accepted

time: 2ms

memory: 5920kb

input:

output:

input:

output:

ok

result:

ok all right

Test #19:

score: 100

Accepted

time: 2ms

memory: 4016kb

input:

output:

input:

output:

ok

result:

ok all right

Test #20:

score: 100

Accepted

time: 0ms

memory: 4024kb

input:

output:

input:

output:

ok

result:

ok all right

Test #21:

score: 100

Accepted

time: 2ms

memory: 5948kb

input:

output:

input:

output:

ok

result:

ok all right

Test #22:

score: 100

Accepted

time: 2ms

memory: 4052kb

input:

output:

input:

output:

ok

result:

ok all right

Test #23:

score: 100

Accepted

time: 2ms

memory: 3936kb

input:

output:

input:

output:

ok

result:

ok all right

Test #24:

score: 100

Accepted

time: 2ms

memory: 4056kb

input:

output:

input:

output:

ok

result:

ok all right

Test #25:

score: 100

Accepted

time: 2ms

memory: 5604kb

input:

output:

input:

output:

ok

result:

ok all right

Test #26:

score: 100

Accepted

time: 2ms

memory: 4072kb

input:

output:

input:

output:

ok

result:

ok all right

Test #27:

score: 100

Accepted

time: 2ms

memory: 3972kb

input:

output:

input:

output:

ok

result:

ok all right

Test #28:

score: 100

Accepted

time: 2ms

memory: 4104kb

input:

output:

input:

output:

ok

result:

ok all right

Test #29:

score: 100

Accepted

time: 2ms

memory: 4012kb

input:

output:

input:

output:

ok

result:

ok all right

Test #30:

score: 100

Accepted

time: 2ms

memory: 4056kb

input:

output:

input:

output:

ok

result:

ok all right

Test #31:

score: 100

Accepted

time: 2ms

memory: 5780kb

input:

output:

input:

output:

ok

result:

ok all right

Test #32:

score: 100

Accepted

time: 2ms

memory: 4092kb

input:

output:

input:

output:

ok

result:

ok all right

Test #33:

score: 100

Accepted

time: 3ms

memory: 5836kb

input:

output:

input:

output:

ok

result:

ok all right

Test #34:

score: 100

Accepted

time: 1ms

memory: 4072kb

input:

output:

input:

output:

ok

result:

ok all right

Test #35:

score: 100

Accepted

time: 2ms

memory: 4064kb

input:

output:

input:

output:

ok

result:

ok all right

Test #36:

score: 100

Accepted

time: 1ms

memory: 3976kb

input:

output:

input:

output:

ok

result:

ok all right

Test #37:

score: 100

Accepted

time: 1ms

memory: 4008kb

input:

output:

input:

output:

ok

result:

ok all right

Test #38:

score: 100

Accepted

time: 1ms

memory: 4048kb

input:

output:

input:

output:

ok

result:

ok all right

Test #39:

score: 100

Accepted

time: 1ms

memory: 3996kb

input:

output:

input:

output:

ok

result:

ok all right

Test #40:

score: 100

Accepted

time: 1ms

memory: 3984kb

input:

output:

input:

output:

ok

result:

ok all right

Test #41:

score: 100

Accepted

time: 1ms

memory: 4064kb

input:

output:

input:

output:

ok

result:

ok all right

Test #42:

score: 100

Accepted

time: 0ms

memory: 4008kb

input:

output:

input:

output:

ok

result:

ok all right

Test #43:

score: 100

Accepted

time: 1ms

memory: 3952kb

input:

output:

input:

output:

ok

result:

ok all right

Test #44:

score: 100

Accepted

time: 1ms

memory: 4044kb

input:

output:

input:

output:

ok

result:

ok all right

Test #45:

score: 100

Accepted

time: 1ms

memory: 3972kb

input:

output:

input:

output:

ok

result:

ok all right

Test #46:

score: 100

Accepted

time: 1ms

memory: 4052kb

input:

output:

input:

output:

ok

result:

ok all right

Test #47:

score: 100

Accepted

time: 1ms

memory: 3976kb

input:

output:

input:

output:

ok

result:

ok all right

Test #48:

score: 100

Accepted

time: 1ms

memory: 4048kb

input:

output:

input:

output:

ok

result:

ok all right

Test #49:

score: 100

Accepted

time: 3ms

memory: 4104kb

input:

output:

input:

output:

ok

result:

ok all right

Test #50:

score: 100

Accepted

time: 3ms

memory: 3960kb

input:

output:

input:

output:

ok

result:

ok all right

Test #51:

score: 100

Accepted

time: 3ms

memory: 4120kb

input:

output:

input:

output:

ok

result:

ok all right

Test #52:

score: 100

Accepted

time: 3ms

memory: 3952kb

input:

output:

input:

output:

ok

result:

ok all right

Test #53:

score: 100

Accepted

time: 3ms

memory: 4020kb

input:

output:

input:

output:

ok

result:

ok all right

Test #54:

score: 100

Accepted

time: 3ms

memory: 4036kb

input:

output:

input:

output:

ok

result:

ok all right

Test #55:

score: 100

Accepted

time: 3ms

memory: 4100kb

input:

output:

input:

output:

ok

result:

ok all right

Test #56:

score: 100

Accepted

time: 3ms

memory: 3996kb

input:

output:

input:

output:

ok

result:

ok all right

Test #57:

score: 100

Accepted

time: 3ms

memory: 3996kb

input:

output:

input:

output:

ok

result:

ok all right

Test #58:

score: 100

Accepted

time: 3ms

memory: 4052kb

input:

output:

input:

output:

ok

result:

ok all right

Test #59:

score: 100

Accepted

time: 2ms

memory: 4104kb

input:

output:

input:

output:

ok

result:

ok all right

Test #60:

score: 100

Accepted

time: 2ms

memory: 4096kb

input:

output:

input:

output:

ok

result:

ok all right

Test #61:

score: 100

Accepted

time: 2ms

memory: 4100kb

input:

output:

input:

output:

ok

result:

ok all right

Test #62:

score: 100

Accepted

time: 3ms

memory: 4116kb

input:

output:

input:

output:

ok

result:

ok all right

Test #63:

score: 100

Accepted

time: 3ms

memory: 4096kb

input:

output:

input:

output:

ok

result:

ok all right