QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #463545 | #63. Meetings | thangthang | 29 | 1062ms | 4456kb | C++20 | 1.3kb | 2024-07-04 23:55:50 | 2024-07-04 23:55:50 |
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){
srand(time(NULL));
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: 3880kb
input:
3 0 2 0 1
output:
Accepted: 1
result:
ok 1 move(s)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
4 1 2 0 2 0 3
output:
Accepted: 2
result:
ok 2 move(s)
Test #3:
score: 0
Accepted
time: 0ms
memory: 4144kb
input:
4 0 3 2 3 0 1
output:
Accepted: 3
result:
ok 3 move(s)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
5 2 4 2 3 0 2 1 3
output:
Accepted: 5
result:
ok 5 move(s)
Test #5:
score: 0
Accepted
time: 0ms
memory: 4156kb
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: 3904kb
input:
6 1 5 2 4 0 4 1 3 3 4
output:
Accepted: 9
result:
ok 9 move(s)
Test #7:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
6 2 4 0 1 0 2 0 5 3 4
output:
Accepted: 10
result:
ok 10 move(s)
Test #8:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
7 1 4 0 6 0 5 1 2 0 3 0 4
output:
Accepted: 10
result:
ok 10 move(s)
Test #9:
score: 0
Accepted
time: 0ms
memory: 4140kb
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: 3880kb
input:
7 3 5 4 5 0 2 2 6 1 2 1 5
output:
Accepted: 10
result:
ok 10 move(s)
Test #11:
score: 0
Accepted
time: 0ms
memory: 3876kb
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: 3920kb
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: 3924kb
input:
7 5 6 1 2 4 5 2 3 3 4 0 1
output:
Accepted: 15
result:
ok 15 move(s)
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #14:
score: 10
Accepted
time: 1ms
memory: 3856kb
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: 671
result:
ok 671 move(s)
Test #15:
score: 0
Accepted
time: 1ms
memory: 4148kb
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: 666
result:
ok 666 move(s)
Test #16:
score: 0
Accepted
time: 1ms
memory: 3876kb
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: 482
result:
ok 482 move(s)
Test #17:
score: 0
Accepted
time: 1ms
memory: 4152kb
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: 861
result:
ok 861 move(s)
Test #18:
score: 0
Accepted
time: 1ms
memory: 3856kb
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: 489
result:
ok 489 move(s)
Test #19:
score: 0
Accepted
time: 1ms
memory: 3888kb
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: 556
result:
ok 556 move(s)
Test #20:
score: 0
Accepted
time: 1ms
memory: 3932kb
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: 952
result:
ok 952 move(s)
Test #21:
score: 0
Accepted
time: 1ms
memory: 3936kb
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: 1017
result:
ok 1017 move(s)
Test #22:
score: 0
Accepted
time: 0ms
memory: 4168kb
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: 1058
result:
ok 1058 move(s)
Test #23:
score: 0
Accepted
time: 0ms
memory: 3860kb
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: 449
result:
ok 449 move(s)
Test #24:
score: 0
Accepted
time: 1ms
memory: 3932kb
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: 422
result:
ok 422 move(s)
Test #25:
score: 0
Accepted
time: 1ms
memory: 3956kb
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: 378
result:
ok 378 move(s)
Test #26:
score: 0
Accepted
time: 1ms
memory: 3860kb
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: 347
result:
ok 347 move(s)
Subtask #3:
score: 12
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #27:
score: 12
Accepted
time: 20ms
memory: 4040kb
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: 16995
result:
ok 16995 move(s)
Test #28:
score: 0
Accepted
time: 14ms
memory: 4000kb
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: 10823
result:
ok 10823 move(s)
Test #29:
score: 0
Accepted
time: 29ms
memory: 4300kb
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: 23922
result:
ok 23922 move(s)
Test #30:
score: 0
Accepted
time: 11ms
memory: 3944kb
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: 9326
result:
ok 9326 move(s)
Test #31:
score: 0
Accepted
time: 28ms
memory: 3992kb
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: 20807
result:
ok 20807 move(s)
Test #32:
score: 0
Accepted
time: 24ms
memory: 4248kb
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: 20880
result:
ok 20880 move(s)
Test #33:
score: 0
Accepted
time: 23ms
memory: 4072kb
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: 19685
result:
ok 19685 move(s)
Test #34:
score: 0
Accepted
time: 12ms
memory: 4236kb
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: 12627
result:
ok 12627 move(s)
Test #35:
score: 0
Accepted
time: 23ms
memory: 4060kb
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: 23639
result:
ok 23639 move(s)
Test #36:
score: 0
Accepted
time: 12ms
memory: 3996kb
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: 11289
result:
ok 11289 move(s)
Test #37:
score: 0
Accepted
time: 18ms
memory: 3968kb
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: 5013
result:
ok 5013 move(s)
Test #38:
score: 0
Accepted
time: 15ms
memory: 3868kb
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: 4220
result:
ok 4220 move(s)
Test #39:
score: 0
Accepted
time: 14ms
memory: 4168kb
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: 3987
result:
ok 3987 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: 1062ms
memory: 4456kb
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