QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#569822	#1148. Game	iframe^#	42	59ms	5964kb	C++17	1.1kb	2024-09-17 11:12:04	2024-09-17 11:12:05

Judging History

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

[2024-09-17 11:12:05]
评测

测评结果：42
用时：59ms
内存：5964kb

查看

[2024-09-17 11:12:04]
提交

answer

#include "game.h"

#include <iostream>

bool used[1500][1500];
bool vis[1500];
int n;

int root[1500];

int find(int i){
	if(root[i] < 0) return i;
	return root[i] = find(root[i]);
}

void merge(int a, int b){
	if(root[a] < root[b]) root[a] += root[b], root[b] = a;
	else root[b] += root[a], root[a] = b;
}

int left(int a, int b){
	int res = 0;
	for(int i=0; i<n; ++i)
		for(int j=i+1; j<n; ++j)
			if((find(i) == a && find(j) == b) ||
			   (find(i) == b && find(j) == a)) ++res;
	return res;
}

void initialize(int N) {
	n = N;
	for(int i=0; i<n; ++i) root[i] = -1;
}

bool dfs(int a, int b){
	if(a == b) return 1;
	if(!used[a][b]) return 1;
	vis[a] = 1;
	for(int i=0; i<n; ++i) if(!used[a][i] && a!=i && !vis[i])
		if(dfs(i, b)) return 1;
	return 0;
}

bool reachable(int a, int b){
	for(int i=0; i<n; ++i) vis[i] = 0;
	return dfs(a, b);
}

int hasEdge(int u, int v) {
	used[u][v] = 1, used[v][u] = 1;

	if(find(u) == find(v)) return 0;

	if(!reachable(u, v)){
		merge(find(u), find(v));
		return 1;
	}

	return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 15

Accepted

Test #1:

score: 15

Accepted

time: 0ms

memory: 3736kb

input:

output:

result:

ok correct

Test #2:

score: 15

Accepted

time: 0ms

memory: 3736kb

input:

output:

result:

ok correct

Test #3:

score: 15

Accepted

time: 0ms

memory: 3704kb

input:

output:

result:

ok correct

Test #4:

score: 15

Accepted

time: 0ms

memory: 3736kb

input:

output:

result:

ok correct

Test #5:

score: 15

Accepted

time: 0ms

memory: 3800kb

input:

output:

result:

ok correct

Test #6:

score: 15

Accepted

time: 0ms

memory: 3704kb

input:

output:

result:

ok correct

Test #7:

score: 15

Accepted

time: 0ms

memory: 3644kb

input:

output:

result:

ok correct

Test #8:

score: 15

Accepted

time: 0ms

memory: 3700kb

input:

output:

result:

ok correct

Test #9:

score: 15

Accepted

time: 0ms

memory: 3848kb

input:

output:

result:

ok correct

Test #10:

score: 15

Accepted

time: 0ms

memory: 3836kb

input:

output:

result:

ok correct

Test #11:

score: 15

Accepted

time: 0ms

memory: 3648kb

input:

output:

result:

ok correct

Test #12:

score: 15

Accepted

time: 0ms

memory: 3732kb

input:

output:

result:

ok correct

Test #13:

score: 15

Accepted

time: 0ms

memory: 3820kb

input:

output:

result:

ok correct

Test #14:

score: 15

Accepted

time: 0ms

memory: 3656kb

input:

output:

result:

ok correct

Test #15:

score: 15

Accepted

time: 0ms

memory: 3648kb

input:

output:

result:

ok correct

Test #16:

score: 15

Accepted

time: 0ms

memory: 3776kb

input:

output:

result:

ok correct

Test #17:

score: 15

Accepted

time: 0ms

memory: 3796kb

input:

output:

result:

ok correct

Test #18:

score: 15

Accepted

time: 0ms

memory: 3844kb

input:

output:

result:

ok correct

Test #19:

score: 15

Accepted

time: 0ms

memory: 3780kb

input:

output:

result:

ok correct

Test #20:

score: 15

Accepted

time: 0ms

memory: 3716kb

input:

output:

result:

ok correct

Test #21:

score: 15

Accepted

time: 0ms

memory: 3800kb

input:

output:

result:

ok correct

Test #22:

score: 15

Accepted

time: 0ms

memory: 3832kb

input:

output:

result:

ok correct

Test #23:

score: 15

Accepted

time: 0ms

memory: 3716kb

input:

output:

result:

ok correct

Test #24:

score: 15

Accepted

time: 0ms

memory: 3736kb

input:

output:

result:

ok correct

Subtask #2:

score: 27

Accepted

Test #25:

score: 27

Accepted

time: 0ms

memory: 3792kb

input:

output:

result:

ok correct

Test #26:

score: 27

Accepted

time: 0ms

memory: 3776kb

input:

output:

result:

ok correct

Test #27:

score: 27

Accepted

time: 0ms

memory: 3748kb

input:

output:

result:

ok correct

Test #28:

score: 27

Accepted

time: 0ms

memory: 3700kb

input:

output:

result:

ok correct

Test #29:

score: 27

Accepted

time: 0ms

memory: 3648kb

input:

output:

result:

ok correct

Test #30:

score: 27

Accepted

time: 0ms

memory: 3800kb

input:

output:

result:

ok correct

Test #31:

score: 27

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok correct

Test #32:

score: 27

Accepted

time: 0ms

memory: 3700kb

input:

output:

result:

ok correct

Test #33:

score: 27

Accepted

time: 0ms

memory: 3732kb

input:

output:

result:

ok correct

Test #34:

score: 27

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok correct

Test #35:

score: 27

Accepted

time: 0ms

memory: 3660kb

input:

output:

result:

ok correct

Test #36:

score: 27

Accepted

time: 0ms

memory: 3796kb

input:

output:

result:

ok correct

Test #37:

score: 27

Accepted

time: 0ms

memory: 3732kb

input:

output:

result:

ok correct

Test #38:

score: 27

Accepted

time: 0ms

memory: 3864kb

input:

output:

result:

ok correct

Test #39:

score: 27

Accepted

time: 0ms

memory: 3648kb

input:

output:

result:

ok correct

Test #40:

score: 27

Accepted

time: 0ms

memory: 3716kb

input:

output:

result:

ok correct

Test #41:

score: 27

Accepted

time: 0ms

memory: 3700kb

input:

output:

result:

ok correct

Test #42:

score: 27

Accepted

time: 0ms

memory: 3772kb

input:

output:

result:

ok correct

Test #43:

score: 27

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok correct

Test #44:

score: 27

Accepted

time: 0ms

memory: 3848kb

input:

output:

result:

ok correct

Test #45:

score: 27

Accepted

time: 0ms

memory: 3776kb

input:

output:

result:

ok correct

Test #46:

score: 27

Accepted

time: 0ms

memory: 3652kb

input:

output:

result:

ok correct

Test #47:

score: 27

Accepted

time: 0ms

memory: 3756kb

input:

output:

result:

ok correct

Test #48:

score: 27

Accepted

time: 0ms

memory: 3800kb

input:

output:

result:

ok correct

Test #49:

score: 27

Accepted

time: 0ms

memory: 3880kb

input:

output:

result:

ok correct

Test #50:

score: 27

Accepted

time: 0ms

memory: 3780kb

input:

output:

result:

ok correct

Test #51:

score: 27

Accepted

time: 0ms

memory: 5916kb

input:

output:

result:

ok correct

Test #52:

score: 27

Accepted

time: 0ms

memory: 3780kb

input:

output:

result:

ok correct

Test #53:

score: 27

Accepted

time: 0ms

memory: 3784kb

input:

output:

result:

ok correct

Test #54:

score: 27

Accepted

time: 0ms

memory: 3780kb

input:

output:

result:

ok correct

Test #55:

score: 27

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok correct

Test #56:

score: 27

Accepted

time: 0ms

memory: 3912kb

input:

output:

result:

ok correct

Test #57:

score: 27

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok correct

Test #58:

score: 27

Accepted

time: 1ms

memory: 3948kb

input:

output:

result:

ok correct

Test #59:

score: 27

Accepted

time: 1ms

memory: 3912kb

input:

output:

result:

ok correct

Test #60:

score: 27

Accepted

time: 1ms

memory: 3852kb

input:

output:

result:

ok correct

Test #61:

score: 27

Accepted

time: 1ms

memory: 3908kb

input:

output:

result:

ok correct

Test #62:

score: 27

Accepted

time: 1ms

memory: 3888kb

input:

output:

result:

ok correct

Test #63:

score: 27

Accepted

time: 1ms

memory: 3852kb

input:

output:

result:

ok correct

Test #64:

score: 27

Accepted

time: 1ms

memory: 3980kb

input:

output:

result:

ok correct

Test #65:

score: 27

Accepted

time: 1ms

memory: 3828kb

input:

output:

result:

ok correct

Test #66:

score: 27

Accepted

time: 1ms

memory: 3764kb

input:

output:

result:

ok correct

Test #67:

score: 27

Accepted

time: 2ms

memory: 3960kb

input:

output:

result:

ok correct

Test #68:

score: 27

Accepted

time: 1ms

memory: 3892kb

input:

output:

result:

ok correct

Test #69:

score: 27

Accepted

time: 1ms

memory: 3888kb

input:

output:

result:

ok correct

Test #70:

score: 27

Accepted

time: 1ms

memory: 3948kb

input:

output:

result:

ok correct

Test #71:

score: 27

Accepted

time: 1ms

memory: 3956kb

input:

output:

result:

ok correct

Test #72:

score: 27

Accepted

time: 1ms

memory: 3816kb

input:

output:

result:

ok correct

Test #73:

score: 27

Accepted

time: 1ms

memory: 3952kb

input:

output:

result:

ok correct

Test #74:

score: 27

Accepted

time: 1ms

memory: 3892kb

input:

output:

result:

ok correct

Test #75:

score: 27

Accepted

time: 1ms

memory: 3960kb

input:

output:

result:

ok correct

Test #76:

score: 27

Accepted

time: 1ms

memory: 3944kb

input:

output:

result:

ok correct

Test #77:

score: 27

Accepted

time: 1ms

memory: 3952kb

input:

output:

result:

ok correct

Test #78:

score: 27

Accepted

time: 1ms

memory: 3848kb

input:

output:

result:

ok correct

Subtask #3:

score: 0

Time Limit Exceeded

Test #79:

score: 58

Accepted

time: 0ms

memory: 3864kb

input:

output:

result:

ok correct

Test #80:

score: 58

Accepted

time: 0ms

memory: 3776kb

input:

output:

result:

ok correct

Test #81:

score: 58

Accepted

time: 0ms

memory: 3796kb

input:

output:

result:

ok correct

Test #82:

score: 58

Accepted

time: 0ms

memory: 3796kb

input:

output:

result:

ok correct

Test #83:

score: 58

Accepted

time: 0ms

memory: 3736kb

input:

output:

result:

ok correct

Test #84:

score: 58

Accepted

time: 0ms

memory: 3800kb

input:

output:

result:

ok correct

Test #85:

score: 58

Accepted

time: 0ms

memory: 3780kb

input:

output:

result:

ok correct

Test #86:

score: 58

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok correct

Test #87:

score: 58

Accepted

time: 0ms

memory: 3736kb

input:

output:

result:

ok correct

Test #88:

score: 58

Accepted

time: 0ms

memory: 3740kb

input:

output:

result:

ok correct

Test #89:

score: 58

Accepted

time: 0ms

memory: 3648kb

input:

output:

result:

ok correct

Test #90:

score: 58

Accepted

time: 0ms

memory: 3872kb

input:

output:

result:

ok correct

Test #91:

score: 58

Accepted

time: 0ms

memory: 3872kb

input:

output:

result:

ok correct

Test #92:

score: 58

Accepted

time: 0ms

memory: 3832kb

input:

output:

result:

ok correct

Test #93:

score: 58

Accepted

time: 0ms

memory: 3792kb

input:

output:

result:

ok correct

Test #94:

score: 58

Accepted

time: 0ms

memory: 3776kb

input:

output:

result:

ok correct

Test #95:

score: 58

Accepted

time: 0ms

memory: 3648kb

input:

output:

result:

ok correct

Test #96:

score: 58

Accepted

time: 0ms

memory: 3656kb

input:

output:

result:

ok correct

Test #97:

score: 58

Accepted

time: 0ms

memory: 3660kb

input:

output:

result:

ok correct

Test #98:

score: 58

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok correct

Test #99:

score: 58

Accepted

time: 0ms

memory: 3840kb

input:

output:

result:

ok correct

Test #100:

score: 58

Accepted

time: 0ms

memory: 3872kb

input:

output:

result:

ok correct

Test #101:

score: 58

Accepted

time: 0ms

memory: 3696kb

input:

output:

result:

ok correct

Test #102:

score: 58

Accepted

time: 0ms

memory: 3732kb

input:

output:

result:

ok correct

Test #103:

score: 58

Accepted

time: 0ms

memory: 3912kb

input:

output:

result:

ok correct

Test #104:

score: 58

Accepted

time: 0ms

memory: 3824kb

input:

output:

result:

ok correct

Test #105:

score: 58

Accepted

time: 0ms

memory: 3836kb

input:

output:

result:

ok correct

Test #106:

score: 58

Accepted

time: 0ms

memory: 3844kb

input:

output:

result:

ok correct

Test #107:

score: 58

Accepted

time: 0ms

memory: 3704kb

input:

output:

result:

ok correct

Test #108:

score: 58

Accepted

time: 0ms

memory: 3912kb

input:

output:

result:

ok correct

Test #109:

score: 58

Accepted

time: 0ms

memory: 3824kb

input:

output:

result:

ok correct

Test #110:

score: 58

Accepted

time: 0ms

memory: 3692kb

input:

output:

result:

ok correct

Test #111:

score: 58

Accepted

time: 0ms

memory: 3888kb

input:

output:

result:

ok correct

Test #112:

score: 58

Accepted

time: 0ms

memory: 3764kb

input:

output:

result:

ok correct

Test #113:

score: 58

Accepted

time: 1ms

memory: 3904kb

input:

output:

result:

ok correct

Test #114:

score: 58

Accepted

time: 0ms

memory: 3956kb

input:

output:

result:

ok correct

Test #115:

score: 58

Accepted

time: 1ms

memory: 3956kb

input:

output:

result:

ok correct

Test #116:

score: 58

Accepted

time: 1ms

memory: 3768kb

input:

output:

result:

ok correct

Test #117:

score: 58

Accepted

time: 1ms

memory: 3960kb

input:

output:

result:

ok correct

Test #118:

score: 58

Accepted

time: 1ms

memory: 3852kb

input:

output:

result:

ok correct

Test #119:

score: 58

Accepted

time: 1ms

memory: 3896kb

input:

output:

result:

ok correct

Test #120:

score: 58

Accepted

time: 1ms

memory: 3888kb

input:

output:

result:

ok correct

Test #121:

score: 58

Accepted

time: 2ms

memory: 3764kb

input:

output:

result:

ok correct

Test #122:

score: 58

Accepted

time: 1ms

memory: 3828kb

input:

output:

result:

ok correct

Test #123:

score: 58

Accepted

time: 1ms

memory: 3848kb

input:

output:

result:

ok correct

Test #124:

score: 58

Accepted

time: 1ms

memory: 3948kb

input:

output:

result:

ok correct

Test #125:

score: 58

Accepted

time: 1ms

memory: 3848kb

input:

output:

result:

ok correct

Test #126:

score: 58

Accepted

time: 1ms

memory: 3888kb

input:

output:

result:

ok correct

Test #127:

score: 58

Accepted

time: 1ms

memory: 3756kb

input:

output:

result:

ok correct

Test #128:

score: 58

Accepted

time: 1ms

memory: 3904kb

input:

output:

result:

ok correct

Test #129:

score: 58

Accepted

time: 1ms

memory: 3948kb

input:

output:

result:

ok correct

Test #130:

score: 58

Accepted

time: 1ms

memory: 3944kb

input:

output:

result:

ok correct

Test #131:

score: 58

Accepted

time: 1ms

memory: 5784kb

input:

output:

result:

ok correct

Test #132:

score: 58

Accepted

time: 1ms

memory: 3848kb

input:

output:

result:

ok correct

Test #133:

score: 58

Accepted

time: 59ms

memory: 5964kb

input:

output:

result:

ok correct

Test #134:

score: 58

Accepted

time: 56ms

memory: 4616kb

input:

output:

result:

ok correct

Test #135:

score: 58

Accepted

time: 53ms

memory: 4608kb

input:

output:

result:

ok correct

Test #136:

score: 58

Accepted

time: 51ms

memory: 4508kb

input:

output:

result:

ok correct

Test #137:

score: 58

Accepted

time: 54ms

memory: 4488kb

input:

output:

result:

ok correct

Test #138:

score: 58

Accepted

time: 52ms

memory: 4424kb

input:

output:

result:

ok correct

Test #139:

score: 58

Accepted

time: 56ms

memory: 4544kb

input:

output:

result:

ok correct

Test #140:

score: 58

Accepted

time: 51ms

memory: 4612kb

input:

output:

result:

ok correct

Test #141:

score: 58

Accepted

time: 55ms

memory: 4608kb

input:

output:

result:

ok correct

Test #142:

score: 0

Time Limit Exceeded

input:

output: