QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#392273	#4686. Tours	oscaryang	AC ✓	1ms	4188kb	C++17	1.4kb	2024-04-17 13:49:16	2024-04-17 13:49:17

Judging History

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

[2024-04-17 13:49:17]
评测

测评结果：AC
用时：1ms
内存：4188kb

查看

[2024-04-17 13:49:16]
提交

answer

#include<bits/stdc++.h>

#define ull unsigned long long
#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;
bool st;

mt19937_64 gen(time(0));

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x; 
}

const int N = 2005;

int n, m, ans, dep[N], cnt[N];
ull val[N];
vc <int> G[N];
map <ull, int> Map;

inline void dfs (int x, int fa = 0) {
	for (auto y : G[x]) if (y != fa) {
		if (!dep[y]) dep[y] = dep[x] + 1, dfs (y, x), val[x] ^= val[y], cnt[x] += cnt[y];
		else if (dep[y] < dep[x]) {
			ans = __gcd (ans, dep[x] - dep[y] + 1);
			ull v = gen (); 
			val[x] ^= v; val[y] ^= v;
			++cnt[x]; --cnt[y];
		}
	}
	if (fa && cnt[x] > 1) ++ Map[val[x]];
}

bool ed;
signed main() {
	cerr << (&ed - &st) / 1024 / 1024 << "MB ---------------------------" << endl;
	
	n = read (); m = read ();
	for (int i = 1, u, v; i <= m; i++)
		u = read (), v = read (), G[u].pb (v), G[v].pb (u);
	
	rep (i, 1, n) if (!dep[i]) dep[i] = 1, dfs (i);
	
	for (auto [u, v] : Map) ans = __gcd (ans, v);
	
	
	rep (i, 1, n) if (ans % i == 0) printf ("%d ", i); 
	putchar (10);
	
	return 0;
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 4020kb

input:

output:

result:

ok 1 number(s): "1"

Test #2:

score: 0

Accepted

time: 0ms

memory: 3972kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"

Test #3:

score: 0

Accepted

time: 0ms

memory: 4020kb

input:

output:

result:

ok 1 number(s): "1"

Test #4:

score: 0

Accepted

time: 0ms

memory: 3976kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"

Test #5:

score: 0

Accepted

time: 0ms

memory: 3964kb

input:

output:

1 2

result:

ok 2 number(s): "1 2"

Test #6:

score: 0

Accepted

time: 0ms

memory: 3952kb

input:

output:

result:

ok 1 number(s): "1"

Test #7:

score: 0

Accepted

time: 0ms

memory: 3976kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"

Test #8:

score: 0

Accepted

time: 0ms

memory: 3980kb

input:

output:

result:

ok 1 number(s): "1"

Test #9:

score: 0

Accepted

time: 1ms

memory: 4188kb

input:

output:

1 2 4 5 8 10 16 20 25 40 50 80 100 125 200 250 400 500 1000 2000

result:

ok 20 numbers

Test #10:

score: 0

Accepted

time: 1ms

memory: 4064kb

input:

output:

1 2 3 6 9 18

result:

ok 6 numbers

Test #11:

score: 0

Accepted

time: 1ms

memory: 4064kb

input:

output:

1 2 3 4 6 12

result:

ok 6 numbers

Test #12:

score: 0

Accepted

time: 1ms

memory: 4168kb

input:

output:

1 3 9

result:

ok 3 number(s): "1 3 9"

Test #13:

score: 0

Accepted

time: 1ms

memory: 4068kb

input:

output:

1 5

result:

ok 2 number(s): "1 5"

Test #14:

score: 0

Accepted

time: 1ms

memory: 3960kb

input:

output:

1 2 4 8

result:

ok 4 number(s): "1 2 4 8"

Test #15:

score: 0

Accepted

time: 1ms

memory: 3880kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"

Test #16:

score: 0

Accepted

time: 1ms

memory: 4072kb

input:

output:

1 7

result:

ok 2 number(s): "1 7"

Test #17:

score: 0

Accepted

time: 0ms

memory: 4008kb

input:

output:

result:

ok 1 number(s): "1"

Test #18:

score: 0

Accepted

time: 0ms

memory: 4008kb

input:

output:

result:

ok 1 number(s): "1"

Test #19:

score: 0

Accepted

time: 1ms

memory: 4168kb

input:

output:

result:

ok 1 number(s): "1"

Test #20:

score: 0

Accepted

time: 1ms

memory: 4056kb

input:

output:

result:

ok 1 number(s): "1"

Test #21:

score: 0

Accepted

time: 1ms

memory: 4160kb

input:

output:

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 30 32 36 40 45 48 60 72 80 90 96 120 144 160 180 240 288 360 480 720 1440

result:

ok 36 numbers

Test #22:

score: 0

Accepted

time: 0ms

memory: 4064kb

input:

1302 1302
893 1045
149 798
202 1034
252 789
269 920
915 989
96 496
1142 1302
647 868
54 1127
161 704
128 1294
51 718
325 825
423 798
344 809
504 1070
548 756
276 1116
8 41
782 1294
602 685
137 976
315 1028
75 562
36 1208
20 302
383 1080
62 392
167 1022
7 126
452 595
791 1182
57 1061
295 842
457 1276...

output:

1 2 3 6 7 14 21 42

result:

ok 8 numbers

Test #23:

score: 0

Accepted

time: 1ms

memory: 4052kb

input:

output:

1 17

result:

ok 2 number(s): "1 17"

Test #24:

score: 0

Accepted

time: 1ms

memory: 4116kb

input:

output:

1 13

result:

ok 2 number(s): "1 13"

Test #25:

score: 0

Accepted

time: 1ms

memory: 3932kb

input:

output:

result:

ok 1 number(s): "1"

Test #26:

score: 0

Accepted

time: 1ms

memory: 3968kb

input:

output:

1 2 3 6

result:

ok 4 number(s): "1 2 3 6"

Test #27:

score: 0

Accepted

time: 1ms

memory: 3988kb

input:

output:

1 3 9

result:

ok 3 number(s): "1 3 9"

Test #28:

score: 0

Accepted

time: 1ms

memory: 3940kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"

Test #29:

score: 0

Accepted

time: 1ms

memory: 4128kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"

Test #30:

score: 0

Accepted

time: 1ms

memory: 3984kb

input:

output:

1 5

result:

ok 2 number(s): "1 5"

Test #31:

score: 0

Accepted

time: 1ms

memory: 3992kb

input:

output:

1 2 4

result:

ok 3 number(s): "1 2 4"

Test #32:

score: 0

Accepted

time: 1ms

memory: 4056kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"

Test #33:

score: 0

Accepted

time: 1ms

memory: 4020kb

input:

output:

1 5

result:

ok 2 number(s): "1 5"

Test #34:

score: 0

Accepted

time: 1ms

memory: 4132kb

input:

output:

1 2 3 6 9 18 37 74 111 222 333 666

result:

ok 12 numbers

Test #35:

score: 0

Accepted

time: 1ms

memory: 4048kb

input:

1652 1988
1297 1437
315 389
138 1096
1317 1474
1310 1315
194 601
939 977
332 1295
275 1502
1039 1326
878 1248
1034 1293
283 454
1372 1452
942 996
1133 1226
285 1111
537 1291
459 1200
799 1074
811 1620
582 1190
714 1376
695 1117
1198 1305
778 869
197 1362
760 1017
1492 1495
709 1400
466 1499
1258 156...

output:

1 2

result:

ok 2 number(s): "1 2"

Test #36:

score: 0

Accepted

time: 1ms

memory: 3988kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"

Test #37:

score: 0

Accepted

time: 1ms

memory: 3976kb

input:

output:

1 2 4

result:

ok 3 number(s): "1 2 4"

Test #38:

score: 0

Accepted

time: 1ms

memory: 4072kb

input:

output:

1 2 5 10

result:

ok 4 number(s): "1 2 5 10"

Test #39:

score: 0

Accepted

time: 1ms

memory: 3980kb

input:

output:

1 2 3 6

result:

ok 4 number(s): "1 2 3 6"

Test #40:

score: 0

Accepted

time: 1ms

memory: 4180kb

input:

output:

1 7

result:

ok 2 number(s): "1 7"

Test #41:

score: 0

Accepted

time: 1ms

memory: 3912kb

input:

output:

result:

ok 1 number(s): "1"

Test #42:

score: 0

Accepted

time: 0ms

memory: 4016kb

input:

output:

1 2

result:

ok 2 number(s): "1 2"

Test #43:

score: 0

Accepted

time: 0ms

memory: 4016kb

input:

output:

result:

ok 1 number(s): "1"

Test #44:

score: 0

Accepted

time: 0ms

memory: 3916kb

input:

output:

result:

ok 1 number(s): "1"

Test #45:

score: 0

Accepted

time: 1ms

memory: 3976kb

input:

output:

1 7

result:

ok 2 number(s): "1 7"

Test #46:

score: 0

Accepted

time: 0ms

memory: 3940kb

input:

output:

1 7

result:

ok 2 number(s): "1 7"

Test #47:

score: 0

Accepted

time: 1ms

memory: 3972kb

input:

output:

1 7

result:

ok 2 number(s): "1 7"

Test #48:

score: 0

Accepted

time: 1ms

memory: 3972kb

input:

output:

1 3 9

result:

ok 3 number(s): "1 3 9"

Test #49:

score: 0

Accepted

time: 0ms

memory: 4008kb

input:

output:

1 13

result:

ok 2 number(s): "1 13"

Test #50:

score: 0

Accepted

time: 0ms

memory: 3968kb

input:

output:

1 5

result:

ok 2 number(s): "1 5"

Test #51:

score: 0

Accepted

time: 0ms

memory: 3888kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"

Test #52:

score: 0

Accepted

time: 1ms

memory: 3956kb

input:

output:

1 2 4

result:

ok 3 number(s): "1 2 4"

Test #53:

score: 0

Accepted

time: 0ms

memory: 4020kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"

Test #54:

score: 0

Accepted

time: 1ms

memory: 4028kb

input:

output:

result:

ok 1 number(s): "1"

Test #55:

score: 0

Accepted

time: 1ms

memory: 4012kb

input:

output:

result:

ok 1 number(s): "1"

Test #56:

score: 0

Accepted

time: 1ms

memory: 4152kb

input:

output:

1 37 41 1517

result:

ok 4 number(s): "1 37 41 1517"

Test #57:

score: 0

Accepted

time: 1ms

memory: 4116kb

input:

output:

1 11 109 1199

result:

ok 4 number(s): "1 11 109 1199"

Test #58:

score: 0

Accepted

time: 1ms

memory: 4076kb

input:

1906 1918
83 1481
34 1495
1339 1894
64 1634
706 1438
1000 1350
456 1174
199 783
450 662
579 1884
980 1373
773 1042
167 680
344 1813
1252 1810
459 604
1338 1816
776 961
659 825
675 685
1160 1872
1147 1383
184 1047
674 1592
262 1687
284 774
611 982
1712 1832
284 409
472 1034
408 559
562 1802
1112 1120...

output:

1 137

result:

ok 2 number(s): "1 137"

Test #59:

score: 0

Accepted

time: 1ms

memory: 4064kb

input:

output:

1 7 13 91

result:

ok 4 number(s): "1 7 13 91"

Test #60:

score: 0

Accepted

time: 1ms

memory: 3948kb

input:

output:

1 19

result:

ok 2 number(s): "1 19"

Test #61:

score: 0

Accepted

time: 1ms

memory: 4020kb

input:

output:

1 2 4 8 16

result:

ok 5 number(s): "1 2 4 8 16"

Test #62:

score: 0

Accepted

time: 1ms

memory: 4064kb

input:

output:

1 2 4 8 16

result:

ok 5 number(s): "1 2 4 8 16"

Test #63:

score: 0

Accepted

time: 1ms

memory: 4052kb

input:

output:

1 2 3 4 6 12

result:

ok 6 numbers

Test #64:

score: 0

Accepted

time: 1ms

memory: 4096kb

input:

output:

1 3

result:

ok 2 number(s): "1 3"