QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#202384	#63. Meetings	james1BadCreeper	100 ✓	640ms	4396kb	C++17	1.2kb	2023-10-05 23:56:01	2023-10-05 23:56:03

Judging History

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

[2023-10-05 23:56:03]
评测

测评结果：100
用时：640ms
内存：4396kb

查看

[2023-10-05 23:56:01]
提交

answer

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

mt19937 Rand(time(0)); 

inline void answer(int x, int y) {
    if (x > y) swap(x, y); 
    Bridge(x, y); 
}

void dfs(vector<int> a, int x, int y) {
    if (a.empty()) return answer(x, y); 
    if (a.size() == 1) return answer(x, a[0]), answer(a[0], y); 
    int mid = a[Rand() % a.size()]; 
    vector<int> al, ar; 
    for (int i : a) if (i != mid) {
        if (Query(x, mid, i) == i) al.emplace_back(i); 
        else ar.emplace_back(i); 
    }
    dfs(al, x, mid); dfs(ar, mid, y); 
}

void solve(vector<int> a) {
    if (a.size() <= 1) return; 
    int n = a.size(), x = a[Rand() % n], y = a[Rand() % n]; 
    while (x == y) y = a[Rand() % n]; 

    map<int, vector<int>> mp; 
    mp[x].emplace_back(x); mp[y].emplace_back(y); 
    for (int i : a) if (i != x && i != y) mp[Query(x, y, i)].emplace_back(i); 
    vector<int> chain; 
    for (auto [p, q] : mp) if (p != x && p != y) chain.emplace_back(p); 
    dfs(chain, x, y); 
    for (auto [p, q] : mp) solve(q); 
}

void Solve(int n) {
    vector<int> a(n); 
    for (int i = 0; i < n; ++i) a[i] = i; 
    solve(a); 
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 7

Accepted

Test #1:

score: 7

Accepted

time: 1ms

memory: 3796kb

input:

3
0 2
0 1

output:

Accepted: 1

result:

ok 1 move(s)

Test #2:

score: 0

Accepted

time: 1ms

memory: 3792kb

input:

output:

Accepted: 3

result:

ok 3 move(s)

Test #3:

score: 0

Accepted

time: 0ms

memory: 3768kb

input:

output:

Accepted: 2

result:

ok 2 move(s)

Test #4:

score: 0

Accepted

time: 0ms

memory: 3780kb

input:

output:

Accepted: 3

result:

ok 3 move(s)

Test #5:

score: 0

Accepted

time: 1ms

memory: 3764kb

input:

output:

Accepted: 4

result:

ok 4 move(s)

Test #6:

score: 0

Accepted

time: 1ms

memory: 3848kb

input:

output:

Accepted: 7

result:

ok 7 move(s)

Test #7:

score: 0

Accepted

time: 0ms

memory: 3816kb

input:

output:

Accepted: 6

result:

ok 6 move(s)

Test #8:

score: 0

Accepted

time: 0ms

memory: 3780kb

input:

output:

Accepted: 7

result:

ok 7 move(s)

Test #9:

score: 0

Accepted

time: 0ms

memory: 3860kb

input:

output:

Accepted: 8

result:

ok 8 move(s)

Test #10:

score: 0

Accepted

time: 0ms

memory: 3796kb

input:

output:

Accepted: 12

result:

ok 12 move(s)

Test #11:

score: 0

Accepted

time: 0ms

memory: 3792kb

input:

output:

Accepted: 9

result:

ok 9 move(s)

Test #12:

score: 0

Accepted

time: 1ms

memory: 3792kb

input:

output:

Accepted: 8

result:

ok 8 move(s)

Test #13:

score: 0

Accepted

time: 1ms

memory: 3884kb

input:

output:

Accepted: 10

result:

ok 10 move(s)

Subtask #2:

score: 10

Accepted

Dependency #1:

100%

Accepted

Test #14:

score: 10

Accepted

time: 1ms

memory: 3804kb

input:

output:

Accepted: 160

result:

ok 160 move(s)

Test #15:

score: 0

Accepted

time: 1ms

memory: 3804kb

input:

output:

Accepted: 223

result:

ok 223 move(s)

Test #16:

score: 0

Accepted

time: 1ms

memory: 3896kb

input:

output:

Accepted: 170

result:

ok 170 move(s)

Test #17:

score: 0

Accepted

time: 1ms

memory: 3856kb

input:

output:

Accepted: 199

result:

ok 199 move(s)

Test #18:

score: 0

Accepted

time: 1ms

memory: 3804kb

input:

output:

Accepted: 132

result:

ok 132 move(s)

Test #19:

score: 0

Accepted

time: 1ms

memory: 3804kb

input:

output:

Accepted: 171

result:

ok 171 move(s)

Test #20:

score: 0

Accepted

time: 1ms

memory: 3804kb

input:

output:

Accepted: 226

result:

ok 226 move(s)

Test #21:

score: 0

Accepted

time: 1ms

memory: 3848kb

input:

output:

Accepted: 345

result:

ok 345 move(s)

Test #22:

score: 0

Accepted

time: 1ms

memory: 3796kb

input:

output:

Accepted: 243

result:

ok 243 move(s)

Test #23:

score: 0

Accepted

time: 1ms

memory: 3856kb

input:

output:

Accepted: 146

result:

ok 146 move(s)

Test #24:

score: 0

Accepted

time: 1ms

memory: 3808kb

input:

output:

Accepted: 204

result:

ok 204 move(s)

Test #25:

score: 0

Accepted

time: 0ms

memory: 3772kb

input:

output:

Accepted: 205

result:

ok 205 move(s)

Test #26:

score: 0

Accepted

time: 1ms

memory: 3772kb

input:

output:

Accepted: 197

result:

ok 197 move(s)

Subtask #3:

score: 12

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #27:

score: 12

Accepted

time: 0ms

memory: 3820kb

input:

output:

Accepted: 1712

result:

ok 1712 move(s)

Test #28:

score: 0

Accepted

time: 2ms

memory: 3760kb

input:

output:

Accepted: 1323

result:

ok 1323 move(s)

Test #29:

score: 0

Accepted

time: 3ms

memory: 3812kb

input:

output:

Accepted: 1368

result:

ok 1368 move(s)

Test #30:

score: 0

Accepted

time: 3ms

memory: 3896kb

input:

output:

Accepted: 1555

result:

ok 1555 move(s)

Test #31:

score: 0

Accepted

time: 3ms

memory: 3884kb

input:

output:

Accepted: 1277

result:

ok 1277 move(s)

Test #32:

score: 0

Accepted

time: 3ms

memory: 3776kb

input:

output:

Accepted: 1700

result:

ok 1700 move(s)

Test #33:

score: 0

Accepted

time: 4ms

memory: 3836kb

input:

output:

Accepted: 2224

result:

ok 2224 move(s)

Test #34:

score: 0

Accepted

time: 5ms

memory: 3840kb

input:

output:

Accepted: 2758

result:

ok 2758 move(s)

Test #35:

score: 0

Accepted

time: 4ms

memory: 3832kb

input:

output:

Accepted: 2615

result:

ok 2615 move(s)

Test #36:

score: 0

Accepted

time: 3ms

memory: 3820kb

input:

output:

Accepted: 1083

result:

ok 1083 move(s)

Test #37:

score: 0

Accepted

time: 7ms

memory: 3856kb

input:

output:

Accepted: 2265

result:

ok 2265 move(s)

Test #38:

score: 0

Accepted

time: 8ms

memory: 3788kb

input:

output:

Accepted: 1926

result:

ok 1926 move(s)

Test #39:

score: 0

Accepted

time: 7ms

memory: 3856kb

input:

output:

Accepted: 2099

result:

ok 2099 move(s)

Subtask #4:

score: 71

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Test #40:

score: 71

Accepted

time: 141ms

memory: 4088kb

input:

output:

Accepted: 13422

result:

ok 13422 move(s)

Test #41:

score: 71

Accepted

time: 154ms

memory: 4128kb

input:

output:

Accepted: 12980

result:

ok 12980 move(s)

Test #42:

score: 71

Accepted

time: 150ms

memory: 4204kb

input:

output:

Accepted: 12721

result:

ok 12721 move(s)

Test #43:

score: 71

Accepted

time: 143ms

memory: 4072kb

input:

output:

Accepted: 12286

result:

ok 12286 move(s)

Test #44:

score: 71

Accepted

time: 174ms

memory: 4112kb

input:

output:

Accepted: 12086

result:

ok 12086 move(s)

Test #45:

score: 71

Accepted

time: 112ms

memory: 4180kb

input:

output:

Accepted: 10588

result:

ok 10588 move(s)

Test #46:

score: 71

Accepted

time: 183ms

memory: 4144kb

input:

2000
1015 1885
353 1472
383 467
705 1492
219 1927
68 1251
290 1215
9 629
331 524
421 1902
87 1901
1283 1982
264 1932
431 1041
746 772
457 822
1551 1901
546 666
290 462
1375 1378
1029 1527
1491 1775
663 1708
663 973
464 1165
834 1365
290 1572
66 1624
813 855
709 984
600 721
615 857
1271 1542
272 1758...

output:

Accepted: 18306

result:

ok 18306 move(s)

Test #47:

score: 71

Accepted

time: 186ms

memory: 4208kb

input:

output:

Accepted: 19983

result:

ok 19983 move(s)

Test #48:

score: 71

Accepted

time: 187ms

memory: 4084kb

input:

output:

Accepted: 21587

result:

ok 21587 move(s)

Test #49:

score: 71

Accepted

time: 184ms

memory: 4196kb

input:

output:

Accepted: 23220

result:

ok 23220 move(s)

Test #50:

score: 71

Accepted

time: 217ms

memory: 4160kb

input:

output:

Accepted: 23278

result:

ok 23278 move(s)

Test #51:

score: 71

Accepted

time: 290ms

memory: 4212kb

input:

output:

Accepted: 12602

result:

ok 12602 move(s)

Test #52:

score: 71

Accepted

time: 162ms

memory: 4184kb

input:

output:

Accepted: 9923

result:

ok 9923 move(s)

Test #53:

score: 71

Accepted

time: 138ms

memory: 4184kb

input:

output:

Accepted: 13944

result:

ok 13944 move(s)

Test #54:

score: 71

Accepted

time: 158ms

memory: 4204kb

input:

output:

Accepted: 15192

result:

ok 15192 move(s)

Test #55:

score: 71

Accepted

time: 166ms

memory: 4124kb

input:

output:

Accepted: 14373

result:

ok 14373 move(s)

Test #56:

score: 71

Accepted

time: 187ms

memory: 4172kb

input:

output:

Accepted: 21652

result:

ok 21652 move(s)

Test #57:

score: 71

Accepted

time: 134ms

memory: 4180kb

input:

output:

Accepted: 14035

result:

ok 14035 move(s)

Test #58:

score: 71

Accepted

time: 149ms

memory: 4168kb

input:

output:

Accepted: 14185

result:

ok 14185 move(s)

Test #59:

score: 71

Accepted

time: 120ms

memory: 4116kb

input:

output:

Accepted: 11312

result:

ok 11312 move(s)

Test #60:

score: 71

Accepted

time: 137ms

memory: 4052kb

input:

output:

Accepted: 12960

result:

ok 12960 move(s)

Test #61:

score: 71

Accepted

time: 137ms

memory: 4112kb

input:

output:

Accepted: 12898

result:

ok 12898 move(s)

Test #62:

score: 71

Accepted

time: 144ms

memory: 4100kb

input:

output:

Accepted: 14570

result:

ok 14570 move(s)

Test #63:

score: 71

Accepted

time: 119ms

memory: 4076kb

input:

output:

Accepted: 12439

result:

ok 12439 move(s)

Test #64:

score: 71

Accepted

time: 149ms

memory: 4108kb

input:

2000
1111 1115
371 387
448 455
1627 1640
1846 1857
234 246
1587 1594
120 134
1329 1332
1785 1799
1357 1370
429 436
1764 1775
509 517
687 697
37 50
548 555
1686 1695
613 624
1968 1981
1627 1629
1846 1852
1785 1801
1974 1985
253 260
76 85
19 37
1826 1829
1212 1215
399 408
1705 1711
1349 1361
1667 1675...

output:

Accepted: 14144

result:

ok 14144 move(s)

Test #65:

score: 71

Accepted

time: 149ms

memory: 4080kb

input:

output:

Accepted: 14492

result:

ok 14492 move(s)

Test #66:

score: 71

Accepted

time: 147ms

memory: 4084kb

input:

output:

Accepted: 14537

result:

ok 14537 move(s)

Test #67:

score: 71

Accepted

time: 217ms

memory: 4168kb

input:

output:

Accepted: 21945

result:

ok 21945 move(s)

Test #68:

score: 71

Accepted

time: 171ms

memory: 4164kb

input:

output:

Accepted: 21576

result:

ok 21576 move(s)

Test #69:

score: 71

Accepted

time: 183ms

memory: 4132kb

input:

output:

Accepted: 22234

result:

ok 22234 move(s)

Test #70:

score: 71

Accepted

time: 204ms

memory: 4172kb

input:

output:

Accepted: 22331

result:

ok 22331 move(s)

Test #71:

score: 71

Accepted

time: 640ms

memory: 4396kb

input:

output:

Accepted: 21505

result:

ok 21505 move(s)

Test #72:

score: 71

Accepted

time: 578ms

memory: 4384kb

input:

output:

Accepted: 20113

result:

ok 20113 move(s)

Extra Test:

score: 0

Extra Test Passed