QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #463363 | #63. Meetings | thangthang | 29 | 1118ms | 4324kb | C++20 | 1.2kb | 2024-07-04 19:03:14 | 2024-07-04 19:03:15 |
Judging History
answer
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T> T rand(T l, T h) { return uniform_int_distribution <T> (l, h) (rng); }
template <class T> T rand(T h) { return uniform_int_distribution <T> (0, h - 1) (rng); }
void cen(vector <int> &cur){
int n = cur.size(); if (n == 1) return;
int root = cur[rand(n)];
vector <vector <int>> sub;
int sz = 0;
for (auto u : cur){
if (u == root) continue;
bool used = false;
for (int i = 0; i < sz; ++ i){
int par = sub[i][0];
int lca = Query(root, par, u);
if (lca == root) continue;
sub[i].push_back(u);
if (lca == u) swap(sub[i][sub[i].size() - 1], sub[i][0]);
used = true;
}
if (!used) {
sub.push_back({u});
++ sz;
}
}
for (int i = 0; i < sz; ++ i){
int u = root;
int v = sub[i][0];
if (u > v) swap(u, v);
Bridge(u, v);
cen(sub[i]);
}
}
void Solve(int N){
vector <int> cur = {};
for (int i = 0; i < N; ++ i) cur.push_back(i);
cen(cur);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 0ms
memory: 3884kb
input:
3 0 2 0 1
output:
Accepted: 1
result:
ok 1 move(s)
Test #2:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
4 1 2 0 2 0 3
output:
Accepted: 3
result:
ok 3 move(s)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
4 0 3 2 3 0 1
output:
Accepted: 3
result:
ok 3 move(s)
Test #4:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
5 2 4 2 3 0 2 1 3
output:
Accepted: 6
result:
ok 6 move(s)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
5 3 4 0 1 0 2 0 3
output:
Accepted: 6
result:
ok 6 move(s)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
6 1 5 2 4 0 4 1 3 3 4
output:
Accepted: 7
result:
ok 7 move(s)
Test #7:
score: 0
Accepted
time: 0ms
memory: 4128kb
input:
6 2 4 0 1 0 2 0 5 3 4
output:
Accepted: 9
result:
ok 9 move(s)
Test #8:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
7 1 4 0 6 0 5 1 2 0 3 0 4
output:
Accepted: 15
result:
ok 15 move(s)
Test #9:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
7 0 4 1 4 2 3 2 4 0 6 2 5
output:
Accepted: 10
result:
ok 10 move(s)
Test #10:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
7 3 5 4 5 0 2 2 6 1 2 1 5
output:
Accepted: 13
result:
ok 13 move(s)
Test #11:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
7 3 6 5 6 4 6 1 6 2 6 0 6
output:
Accepted: 15
result:
ok 15 move(s)
Test #12:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
7 2 3 0 5 4 6 1 6 0 2 3 4
output:
Accepted: 15
result:
ok 15 move(s)
Test #13:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
7 5 6 1 2 4 5 2 3 3 4 0 1
output:
Accepted: 11
result:
ok 11 move(s)
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #14:
score: 10
Accepted
time: 1ms
memory: 4128kb
input:
50 25 32 16 48 36 46 13 48 18 27 18 30 9 29 19 47 30 35 2 36 1 49 33 34 41 47 11 13 7 10 17 38 2 18 1 15 1 33 4 23 8 11 36 47 14 20 25 39 5 7 12 48 2 45 21 47 0 21 1 23 19 43 32 33 4 14 22 36 38 46 5 28 1 29 2 31 3 4 40 47 34 44 34 42 24 43 33 36 11 26 6 11 7 47 37 38 1 6
output:
Accepted: 722
result:
ok 722 move(s)
Test #15:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
49 10 47 29 42 18 38 21 45 11 17 8 34 8 46 27 31 29 32 14 30 5 28 36 41 20 24 17 27 13 45 3 38 7 34 1 8 27 40 0 7 22 34 11 23 13 28 14 35 24 47 3 43 2 33 0 37 18 44 3 7 2 26 4 17 23 41 28 30 3 17 28 32 17 26 16 31 6 17 19 30 9 25 4 12 42 48 17 28 17 47 17 39 2 15 7 25
output:
Accepted: 638
result:
ok 638 move(s)
Test #16:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
48 6 19 1 33 34 44 29 30 27 35 8 40 17 39 8 47 11 46 14 40 17 32 8 23 26 40 9 27 4 8 11 39 33 38 8 15 21 40 2 41 7 11 20 26 12 28 16 24 31 41 18 24 34 46 0 40 34 38 5 15 10 34 18 45 26 29 40 43 35 47 6 21 28 34 8 41 8 42 14 18 22 30 3 14 34 37 13 46 14 36 17 25 8 46
output:
Accepted: 744
result:
ok 744 move(s)
Test #17:
score: 0
Accepted
time: 1ms
memory: 3884kb
input:
50 15 16 25 42 41 42 31 48 44 45 7 43 7 30 1 19 13 26 0 23 4 38 18 49 40 41 8 42 7 38 14 33 18 19 2 47 3 15 1 3 30 47 3 7 1 26 20 38 21 36 3 25 39 42 28 45 3 45 6 8 33 48 6 17 25 35 29 47 12 29 1 34 21 46 17 37 41 46 3 22 5 45 1 31 7 24 32 38 11 30 27 36 0 39 3 9 10 20
output:
Accepted: 589
result:
ok 589 move(s)
Test #18:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
50 29 46 2 21 3 16 22 31 11 49 2 43 36 40 7 17 1 46 30 32 42 49 5 15 7 44 6 12 20 46 23 30 21 23 26 27 28 34 7 10 6 20 38 42 39 45 2 8 8 33 20 39 19 43 30 35 14 38 3 12 17 47 13 26 12 21 25 49 0 40 27 40 28 47 5 47 16 17 22 24 37 38 16 42 22 23 39 48 6 27 18 26 8 9 4 43 5 41
output:
Accepted: 675
result:
ok 675 move(s)
Test #19:
score: 0
Accepted
time: 0ms
memory: 4092kb
input:
50 32 36 23 29 27 37 33 48 0 17 17 49 38 41 17 19 6 17 20 29 27 38 10 29 12 36 11 40 16 48 36 38 11 38 30 48 27 34 11 15 29 38 17 38 35 48 9 48 13 36 18 48 3 11 4 48 29 42 11 39 8 29 11 28 17 24 5 27 31 36 36 43 29 47 27 46 14 17 11 44 22 36 21 36 7 17 29 45 11 25 2 27 1 27 26 27 38 48
output:
Accepted: 837
result:
ok 837 move(s)
Test #20:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
49 24 42 4 21 2 21 12 48 16 24 24 45 6 21 21 46 21 23 20 24 22 24 21 38 14 24 12 25 24 30 21 24 12 39 31 32 0 31 11 21 12 37 12 36 9 31 18 24 24 47 24 35 7 24 12 27 13 21 12 33 12 21 5 12 21 41 3 12 21 31 24 26 12 29 10 12 24 28 24 44 1 21 17 21 8 12 12 15 24 34 19 21 12 40 12 43
output:
Accepted: 986
result:
ok 986 move(s)
Test #21:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
50 10 36 39 42 23 39 8 39 24 43 24 46 10 17 33 39 10 38 10 41 10 45 10 40 10 16 28 39 10 24 14 39 4 24 18 39 7 39 26 39 10 44 1 24 21 24 9 24 13 39 10 31 39 48 24 37 24 35 19 24 10 27 39 49 25 39 2 24 39 47 10 20 24 39 3 10 0 24 10 29 6 24 10 12 22 24 10 30 34 39 15 24 10 11 24 32 5 10
output:
Accepted: 1092
result:
ok 1092 move(s)
Test #22:
score: 0
Accepted
time: 1ms
memory: 4132kb
input:
50 14 29 13 43 13 37 13 40 5 14 1 13 22 34 13 24 13 23 3 14 2 13 34 41 14 36 18 34 31 34 34 45 13 39 14 21 14 19 13 33 14 20 34 46 13 32 15 34 0 14 34 35 14 42 14 25 13 49 11 13 34 44 13 28 7 34 14 34 4 34 13 47 14 38 9 14 6 34 26 34 8 13 13 14 27 34 14 16 13 17 10 13 14 48 12 14 30 34
output:
Accepted: 919
result:
ok 919 move(s)
Test #23:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
50 3 20 11 12 9 33 17 24 13 49 5 36 10 47 4 48 41 44 14 16 9 48 6 16 12 18 6 30 2 23 2 40 31 41 1 17 3 21 25 37 34 39 44 49 19 42 7 27 7 15 20 35 18 24 14 32 1 32 9 43 0 29 22 38 34 38 12 21 42 48 17 31 29 45 22 49 8 42 28 34 10 11 10 37 4 32 3 5 13 27 5 26 14 46 16 29 2 46
output:
Accepted: 728
result:
ok 728 move(s)
Test #24:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
50 20 46 25 39 4 22 8 17 10 47 1 23 41 48 14 20 15 39 4 21 45 49 13 45 33 42 34 35 36 41 29 31 30 44 29 32 3 32 16 49 27 38 27 47 0 10 8 37 9 18 9 43 0 44 11 25 12 31 37 46 5 19 28 43 13 17 6 21 28 40 23 26 2 24 33 48 2 18 5 40 7 30 6 16 1 19 24 34 14 42 7 26 15 22 11 12 3 35
output:
Accepted: 400
result:
ok 400 move(s)
Test #25:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
50 28 42 10 23 31 36 38 48 30 45 15 49 14 21 24 36 25 35 16 43 19 49 6 17 15 43 29 39 9 27 8 13 37 45 37 44 7 20 4 25 22 26 6 46 13 38 11 19 3 33 4 28 8 40 1 5 10 31 0 1 2 20 24 32 14 27 3 26 18 47 11 41 7 42 12 17 16 23 5 12 2 34 32 34 21 33 39 41 35 40 0 22 44 47 30 48 29 46
output:
Accepted: 411
result:
ok 411 move(s)
Test #26:
score: 0
Accepted
time: 1ms
memory: 4116kb
input:
50 43 44 16 17 32 33 9 10 15 16 26 27 24 25 18 19 45 46 37 38 28 29 44 45 36 37 27 28 0 1 10 11 8 9 5 6 46 47 34 35 39 40 40 41 38 39 19 20 1 2 7 8 35 36 33 34 48 49 17 18 3 4 47 48 22 23 4 5 14 15 6 7 42 43 2 3 31 32 13 14 25 26 23 24 30 31 20 21 11 12 29 30 21 22 12 13 41 42
output:
Accepted: 327
result:
ok 327 move(s)
Subtask #3:
score: 12
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #27:
score: 12
Accepted
time: 29ms
memory: 4260kb
input:
300 191 265 158 220 169 267 75 180 82 215 171 245 68 142 229 246 72 89 85 222 123 156 103 245 47 65 260 272 55 240 66 262 119 185 85 110 120 173 114 217 38 288 247 292 68 203 239 285 208 275 123 157 124 142 50 265 181 258 55 272 0 27 25 48 225 250 66 181 165 259 37 154 32 176 17 121 70 131 40 76 10 ...
output:
Accepted: 22682
result:
ok 22682 move(s)
Test #28:
score: 0
Accepted
time: 22ms
memory: 3960kb
input:
299 13 145 175 235 8 55 133 286 73 147 89 103 47 241 82 151 23 98 158 202 19 94 57 221 117 198 8 210 47 258 93 198 105 255 95 236 83 208 100 124 166 253 137 280 1 76 176 236 165 226 14 15 56 195 45 183 281 282 58 216 39 102 46 234 4 210 37 149 126 293 212 234 90 284 81 121 33 276 152 264 99 241 7 21...
output:
Accepted: 17360
result:
ok 17360 move(s)
Test #29:
score: 0
Accepted
time: 22ms
memory: 4220kb
input:
298 165 206 60 250 121 218 73 228 156 163 6 124 199 200 123 238 6 263 17 163 147 250 40 63 8 206 124 126 111 285 112 203 217 260 83 151 28 241 18 279 172 224 112 121 116 189 66 138 216 243 125 225 181 255 97 232 93 229 74 138 55 90 204 264 84 248 77 221 4 142 101 191 182 276 35 199 150 284 120 241 1...
output:
Accepted: 16940
result:
ok 16940 move(s)
Test #30:
score: 0
Accepted
time: 20ms
memory: 3916kb
input:
300 71 228 160 285 48 87 33 266 151 195 72 113 124 134 47 125 32 286 185 294 80 89 30 154 78 158 182 260 106 293 164 242 151 224 98 293 100 277 53 267 1 258 134 248 51 235 49 50 265 270 69 274 155 188 72 191 71 268 165 209 87 190 134 215 125 295 139 284 79 178 63 77 272 297 118 180 146 237 159 224 1...
output:
Accepted: 15387
result:
ok 15387 move(s)
Test #31:
score: 0
Accepted
time: 14ms
memory: 4024kb
input:
300 59 259 72 136 138 231 87 126 128 148 70 189 199 284 100 118 125 185 190 278 92 99 129 267 241 270 139 160 89 189 234 236 23 84 100 212 110 186 27 198 258 277 45 164 172 299 10 286 48 135 92 255 125 227 49 263 39 141 29 130 95 298 5 296 211 250 76 223 98 189 183 202 132 137 54 157 112 291 210 245...
output:
Accepted: 9719
result:
ok 9719 move(s)
Test #32:
score: 0
Accepted
time: 34ms
memory: 4292kb
input:
300 170 212 80 293 192 236 86 289 43 181 244 298 121 124 169 218 260 262 48 191 184 272 84 96 48 224 15 113 20 236 70 292 96 100 77 122 8 24 73 162 20 278 34 134 22 218 74 181 261 292 150 193 81 171 20 277 94 122 30 280 166 236 63 178 42 249 146 171 72 260 71 214 145 149 225 297 67 162 0 5 24 191 2 ...
output:
Accepted: 32136
result:
ok 32136 move(s)
Test #33:
score: 0
Accepted
time: 41ms
memory: 4084kb
input:
299 10 212 34 69 97 294 124 186 135 288 52 212 77 140 71 108 100 241 19 94 220 294 101 204 204 285 1 135 19 72 184 294 117 147 18 19 124 158 96 124 80 207 11 124 114 291 124 211 57 120 53 120 32 124 143 220 63 100 124 191 135 286 128 135 0 80 23 137 71 164 120 267 100 162 65 71 51 171 51 75 100 225 ...
output:
Accepted: 32864
result:
ok 32864 move(s)
Test #34:
score: 0
Accepted
time: 40ms
memory: 4068kb
input:
300 83 89 145 259 133 149 255 277 203 269 226 241 102 262 83 183 149 191 83 285 70 160 248 262 36 277 259 263 139 200 104 228 146 226 99 228 183 218 97 228 16 40 30 218 123 149 214 277 122 262 131 139 269 290 149 229 9 40 183 259 160 183 54 286 62 83 125 269 37 83 28 136 149 242 38 160 110 259 95 25...
output:
Accepted: 32926
result:
ok 32926 move(s)
Test #35:
score: 0
Accepted
time: 36ms
memory: 4240kb
input:
300 56 123 98 191 13 22 186 221 132 248 32 158 103 222 22 290 43 139 148 236 12 22 47 123 40 221 132 253 235 251 123 173 222 225 23 86 18 271 23 41 212 291 124 221 213 236 125 212 211 222 150 191 17 233 96 123 128 214 23 30 7 161 5 251 43 141 132 249 27 191 18 42 212 279 43 144 230 247 22 134 230 28...
output:
Accepted: 25992
result:
ok 25992 move(s)
Test #36:
score: 0
Accepted
time: 15ms
memory: 4040kb
input:
300 153 237 93 255 238 285 159 259 165 227 123 297 110 111 187 193 32 34 71 103 72 156 8 136 28 45 28 71 150 299 113 221 212 246 139 255 130 208 61 223 15 234 26 66 167 285 150 266 231 238 73 165 44 263 18 113 200 278 161 205 11 31 58 249 134 268 155 259 229 288 121 249 220 232 14 105 131 225 52 235...
output:
Accepted: 10383
result:
ok 10383 move(s)
Test #37:
score: 0
Accepted
time: 10ms
memory: 3880kb
input:
300 121 184 29 35 146 251 28 34 100 180 135 171 9 126 9 65 8 117 23 91 57 114 90 202 94 273 12 192 187 263 199 271 71 107 53 78 108 178 67 83 50 121 5 21 51 244 101 261 217 269 138 212 241 288 21 120 4 127 68 254 167 207 44 276 53 93 90 197 66 152 24 188 174 256 200 209 20 75 147 275 31 157 55 86 3 ...
output:
Accepted: 4040
result:
ok 4040 move(s)
Test #38:
score: 0
Accepted
time: 16ms
memory: 3960kb
input:
300 110 202 68 161 51 183 286 296 230 288 91 195 240 277 148 176 50 92 81 143 242 262 182 292 148 212 77 234 212 285 105 126 33 219 11 61 17 25 144 227 124 265 58 195 76 186 6 132 67 74 133 299 155 276 226 264 53 284 26 241 36 185 71 177 256 299 53 86 2 13 110 134 67 165 146 198 59 185 23 194 42 276...
output:
Accepted: 4482
result:
ok 4482 move(s)
Test #39:
score: 0
Accepted
time: 13ms
memory: 3940kb
input:
300 178 179 145 146 293 294 127 128 220 221 222 223 135 136 195 196 97 98 221 222 162 163 291 292 201 202 257 258 51 52 272 273 76 77 274 275 46 47 285 286 263 264 255 256 3 4 96 97 141 142 82 83 74 75 44 45 52 53 57 58 92 93 228 229 104 105 94 95 2 3 140 141 54 55 177 178 183 184 112 113 28 29 283 ...
output:
Accepted: 3697
result:
ok 3697 move(s)
Subtask #4:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #40:
score: 0
Wrong Answer
time: 1118ms
memory: 4324kb
input:
2000 58 503 623 1403 1004 1083 249 491 1524 1849 192 562 1261 1877 547 909 267 896 747 1986 381 1329 57 317 779 886 469 1652 628 1456 1732 1790 700 825 494 1799 1450 1733 103 1069 1114 1342 243 1496 930 1361 240 905 398 1737 1008 1765 357 954 1157 1898 1228 1344 1062 1731 160 1977 40 364 343 694 108...
output:
Wrong Answer [2]
result:
wrong answer