QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#295060	#4829. Mark on a Graph	ucup-team191^#	AC ✓	3ms	8404kb	C++14	1.5kb	2023-12-30 18:14:09	2023-12-30 18:14:11

Judging History

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

[2023-12-30 18:14:11]
评测

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

查看

[2023-12-30 18:14:09]
提交

answer

#include <cstdio>
#include <vector>

#define PB push_back

using namespace std;

const int N = 1e3 + 50;

vector < int > v[N];
vector < int > g[N];
vector < int > moji;
int uzeo[N], spojen[N][N], deg[N];
int n, m;

vector < int > put;

bool brut() {
	if((int)put.size() == 5) return spojen[put[0]][put.back()];
	for(int z : g[put.back()]) {
		if(uzeo[z] != 2) {
			uzeo[z] = 2; put.PB(z);
			if(brut()) return true;
			uzeo[z] = 1; put.pop_back();
		}
	}
	return false;
}

bool postoji_kurac(int x){
	for(int y : v[x]) uzeo[y] = 1;
	for(int y : v[x]) {
		g[y].clear();
		for(int z : v[y])
			if(uzeo[z]) g[y].PB(z);
	}
	for(int y : v[x]) {
		put.PB(y);
		if(brut()) {
			return true;
		}
		put.pop_back();
	}
	for(int y : v[x]) uzeo[y] = 0;
	return false;		
}

int main(){
	scanf("%d%d", &n, &m);
	//if(m < 2000 || m > 5000) {
	//	printf("ok\n");
	//	return 0;
	//}
	for(int i = 0;i < m;i++) {
		int a, b; scanf("%d%d", &a, &b);
		v[a].PB(b), v[b].PB(a);
		spojen[a][b] = 1; spojen[b][a] = 1;
		deg[a]++; deg[b]++;
	}
	int pos = 0;
	for(int i = 1;i <= n;i++) {
		if(deg[i] >= 5)	pos = i;
		if(deg[i] >= 5 && postoji_kurac(i)) {
			printf("ok\n");
			return 0;
		}
	}
	printf("mark\n");
	vector < int > stoA, stoB;
	for(int i = 0;i < 5;i++) {
		int j = (i + 1) % 5;
		if(!spojen[v[pos][i]][v[pos][j]]) {
			stoA.PB(v[pos][i]);
			stoB.PB(v[pos][j]);
		}
	}
	printf("%d\n", (int)stoA.size());
	for(int i = 0;i < (int)stoA.size();i++)
		printf("%d %d\n", stoA[i], stoB[i]);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 8020kb

input:

output:

input:

output:

ok

result:

ok all right

Test #2:

score: 100

Accepted

time: 1ms

memory: 8172kb

input:

output:

input:

output:

ok

result:

ok all right

Test #3:

score: 100

Accepted

time: 2ms

memory: 8096kb

input:

output:

input:

output:

ok

result:

ok all right

Test #4:

score: 100

Accepted

time: 2ms

memory: 8032kb

input:

output:

input:

output:

ok

result:

ok all right

Test #5:

score: 100

Accepted

time: 2ms

memory: 7976kb

input:

output:

input:

output:

ok

result:

ok all right

Test #6:

score: 100

Accepted

time: 2ms

memory: 8028kb

input:

output:

input:

output:

ok

result:

ok all right

Test #7:

score: 100

Accepted

time: 2ms

memory: 8036kb

input:

output:

input:

output:

ok

result:

ok all right

Test #8:

score: 100

Accepted

time: 3ms

memory: 8064kb

input:

output:

input:

output:

ok

result:

ok all right

Test #9:

score: 100

Accepted

time: 3ms

memory: 8120kb

input:

output:

input:

output:

ok

result:

ok all right

Test #10:

score: 100

Accepted

time: 3ms

memory: 8256kb

input:

output:

input:

output:

ok

result:

ok all right

Test #11:

score: 100

Accepted

time: 0ms

memory: 8036kb

input:

output:

input:

output:

ok

result:

ok all right

Test #12:

score: 100

Accepted

time: 2ms

memory: 8060kb

input:

output:

input:

output:

ok

result:

ok all right

Test #13:

score: 100

Accepted

time: 2ms

memory: 8004kb

input:

output:

input:

output:

ok

result:

ok all right

Test #14:

score: 100

Accepted

time: 2ms

memory: 8052kb

input:

output:

input:

output:

ok

result:

ok all right

Test #15:

score: 100

Accepted

time: 2ms

memory: 8000kb

input:

output:

input:

output:

ok

result:

ok all right

Test #16:

score: 100

Accepted

time: 2ms

memory: 8292kb

input:

output:

input:

output:

ok

result:

ok all right

Test #17:

score: 100

Accepted

time: 2ms

memory: 8028kb

input:

output:

input:

output:

ok

result:

ok all right

Test #18:

score: 100

Accepted

time: 3ms

memory: 8232kb

input:

output:

input:

output:

ok

result:

ok all right

Test #19:

score: 100

Accepted

time: 2ms

memory: 8028kb

input:

output:

input:

output:

ok

result:

ok all right

Test #20:

score: 100

Accepted

time: 2ms

memory: 8316kb

input:

output:

input:

output:

ok

result:

ok all right

Test #21:

score: 100

Accepted

time: 2ms

memory: 8404kb

input:

output:

input:

output:

ok

result:

ok all right

Test #22:

score: 100

Accepted

time: 2ms

memory: 8076kb

input:

output:

input:

output:

ok

result:

ok all right

Test #23:

score: 100

Accepted

time: 2ms

memory: 8048kb

input:

output:

input:

output:

ok

result:

ok all right

Test #24:

score: 100

Accepted

time: 2ms

memory: 7940kb

input:

output:

input:

output:

ok

result:

ok all right

Test #25:

score: 100

Accepted

time: 2ms

memory: 8068kb

input:

output:

input:

output:

ok

result:

ok all right

Test #26:

score: 100

Accepted

time: 2ms

memory: 8316kb

input:

output:

input:

output:

ok

result:

ok all right

Test #27:

score: 100

Accepted

time: 2ms

memory: 8192kb

input:

output:

input:

output:

ok

result:

ok all right

Test #28:

score: 100

Accepted

time: 2ms

memory: 8312kb

input:

output:

input:

output:

ok

result:

ok all right

Test #29:

score: 100

Accepted

time: 2ms

memory: 8060kb

input:

output:

input:

output:

ok

result:

ok all right

Test #30:

score: 100

Accepted

time: 2ms

memory: 8252kb

input:

output:

input:

output:

ok

result:

ok all right

Test #31:

score: 100

Accepted

time: 2ms

memory: 8188kb

input:

output:

input:

output:

ok

result:

ok all right

Test #32:

score: 100

Accepted

time: 2ms

memory: 8248kb

input:

output:

input:

output:

ok

result:

ok all right

Test #33:

score: 100

Accepted

time: 2ms

memory: 8264kb

input:

output:

input:

output:

ok

result:

ok all right

Test #34:

score: 100

Accepted

time: 2ms

memory: 8224kb

input:

output:

input:

output:

ok

result:

ok all right

Test #35:

score: 100

Accepted

time: 0ms

memory: 8016kb

input:

output:

input:

output:

ok

result:

ok all right

Test #36:

score: 100

Accepted

time: 2ms

memory: 8012kb

input:

output:

input:

output:

ok

result:

ok all right

Test #37:

score: 100

Accepted

time: 2ms

memory: 7940kb

input:

output:

input:

output:

ok

result:

ok all right

Test #38:

score: 100

Accepted

time: 2ms

memory: 8252kb

input:

output:

input:

output:

ok

result:

ok all right

Test #39:

score: 100

Accepted

time: 2ms

memory: 7972kb

input:

output:

input:

output:

ok

result:

ok all right

Test #40:

score: 100

Accepted

time: 2ms

memory: 8244kb

input:

output:

input:

output:

ok

result:

ok all right

Test #41:

score: 100

Accepted

time: 1ms

memory: 8144kb

input:

output:

input:

output:

ok

result:

ok all right

Test #42:

score: 100

Accepted

time: 2ms

memory: 8028kb

input:

output:

input:

output:

ok

result:

ok all right

Test #43:

score: 100

Accepted

time: 2ms

memory: 8032kb

input:

output:

input:

output:

ok

result:

ok all right

Test #44:

score: 100

Accepted

time: 2ms

memory: 8256kb

input:

output:

input:

output:

ok

result:

ok all right

Test #45:

score: 100

Accepted

time: 2ms

memory: 8184kb

input:

output:

input:

output:

ok

result:

ok all right

Test #46:

score: 100

Accepted

time: 2ms

memory: 7928kb

input:

output:

input:

output:

ok

result:

ok all right

Test #47:

score: 100

Accepted

time: 2ms

memory: 7948kb

input:

output:

input:

output:

ok

result:

ok all right

Test #48:

score: 100

Accepted

time: 2ms

memory: 8008kb

input:

output:

input:

output:

ok

result:

ok all right

Test #49:

score: 100

Accepted

time: 2ms

memory: 8064kb

input:

output:

input:

output:

ok

result:

ok all right

Test #50:

score: 100

Accepted

time: 2ms

memory: 8124kb

input:

output:

input:

output:

ok

result:

ok all right

Test #51:

score: 100

Accepted

time: 2ms

memory: 8052kb

input:

output:

input:

output:

ok

result:

ok all right

Test #52:

score: 100

Accepted

time: 2ms

memory: 8104kb

input:

output:

input:

output:

ok

result:

ok all right

Test #53:

score: 100

Accepted

time: 2ms

memory: 8240kb

input:

output:

input:

output:

ok

result:

ok all right

Test #54:

score: 100

Accepted

time: 0ms

memory: 8068kb

input:

output:

input:

output:

ok

result:

ok all right

Test #55:

score: 100

Accepted

time: 2ms

memory: 8232kb

input:

output:

input:

output:

ok

result:

ok all right

Test #56:

score: 100

Accepted

time: 2ms

memory: 8336kb

input:

output:

input:

output:

ok

result:

ok all right

Test #57:

score: 100

Accepted

time: 2ms

memory: 8268kb

input:

output:

input:

output:

ok

result:

ok all right

Test #58:

score: 100

Accepted

time: 3ms

memory: 8272kb

input:

output:

input:

output:

ok

result:

ok all right

Test #59:

score: 100

Accepted

time: 2ms

memory: 8104kb

input:

output:

input:

output:

ok

result:

ok all right

Test #60:

score: 100

Accepted

time: 2ms

memory: 8232kb

input:

output:

input:

output:

ok

result:

ok all right

Test #61:

score: 100

Accepted

time: 2ms

memory: 7988kb

input:

output:

input:

output:

ok

result:

ok all right

Test #62:

score: 100

Accepted

time: 2ms

memory: 8204kb

input:

output:

input:

output:

ok

result:

ok all right

Test #63:

score: 100

Accepted

time: 3ms

memory: 8068kb

input:

output:

input:

output:

ok

result:

ok all right