QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #463345 | #63. Meetings | thangthang | 29 | 1104ms | 4588kb | C++20 | 3.3kb | 2024-07-04 18:34:50 | 2024-07-04 18:34:51 |
Judging History
answer
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
//namespace {
//
//const int MAX_N = 2000;
//const int MAX_CALLS = 100000;
//
//void WrongAnswer(int code) {
// printf("Wrong Answer [%d]\n", code);
// exit(0);
//}
//
//int N, num_calls;
//std::vector<int> graph[MAX_N];
//std::set<std::pair<int, int>> edges, edges_reported;
//
//int weight[MAX_N];
//
////mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
////#define rand rd
////
////long long Rand(long long l, long long h) {
//// assert(l <= h);
//// return l + rd() * 1LL * rd() % (h - l + 1);
////}
//
//bool Visit(int p, int e, int rt = -1) {
// if (p == e) {
// ++weight[p];
// return true;
// }
// for (int q : graph[p]) {
// if (q != rt) {
// if (Visit(q, e, p)) {
// ++weight[p];
// return true;
// }
// }
// }
// return false;
//}
//
//int Query(int u, int v, int w) {
// if (!(0 <= u && u <= N - 1 && 0 <= v && v <= N - 1 && 0 <= w && w <= N - 1 &&
// u != v && u != w && v != w)) {
// WrongAnswer(1);
// }
// if (++num_calls > MAX_CALLS) {
// WrongAnswer(2);
// }
// std::fill(weight, weight + N, 0);
// Visit(u, v);
// Visit(u, w);
// Visit(v, w);
// for (int x = 0; x < N; ++x) {
// if (weight[x] == 3) {
// return x;
// }
// }
// printf("Error: the input may be invalid\n");
// exit(0);
//}
//
//void Bridge(int u, int v) {
// if (!(0 <= u && u < v && v <= N - 1)) {
// WrongAnswer(3);
// }
// if (!(edges.count(std::make_pair(u, v)) >= 1)) {
// WrongAnswer(4);
// }
// if (!(edges_reported.count(std::make_pair(u, v)) == 0)) {
// WrongAnswer(5);
// }
// edges_reported.insert(std::make_pair(u, v));
//}
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);
}
//} // namespace
//
//int main() {
// if (scanf("%d", &N) != 1) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// for (int i = 0; i < N - 1; ++i) {
// int u, v;
// if (scanf("%d%d", &u, &v) != 2) {
// fprintf(stderr, "Error while reading input\n");
// exit(1);
// }
// graph[u].push_back(v);
// graph[v].push_back(u);
// edges.insert(std::make_pair(u, v));
// }
//
// num_calls = 0;
// Solve(N);
// if (edges_reported.size() != static_cast<size_t>(N - 1)) {
// WrongAnswer(6);
// }
// printf("Accepted: %d\n", num_calls);
// return 0;
//}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 0ms
memory: 3828kb
input:
3 0 2 0 1
output:
Accepted: 1
result:
ok 1 move(s)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
4 1 2 0 2 0 3
output:
Accepted: 3
result:
ok 3 move(s)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
4 0 3 2 3 0 1
output:
Accepted: 2
result:
ok 2 move(s)
Test #4:
score: 0
Accepted
time: 0ms
memory: 4124kb
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: 3836kb
input:
5 3 4 0 1 0 2 0 3
output:
Accepted: 4
result:
ok 4 move(s)
Test #6:
score: 0
Accepted
time: 0ms
memory: 3828kb
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: 3916kb
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: 4132kb
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: 3836kb
input:
7 0 4 1 4 2 3 2 4 0 6 2 5
output:
Accepted: 15
result:
ok 15 move(s)
Test #10:
score: 0
Accepted
time: 0ms
memory: 3832kb
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: 3792kb
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: 3824kb
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: 4100kb
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: 4140kb
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: 482
result:
ok 482 move(s)
Test #15:
score: 0
Accepted
time: 1ms
memory: 3848kb
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: 576
result:
ok 576 move(s)
Test #16:
score: 0
Accepted
time: 1ms
memory: 3844kb
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: 861
result:
ok 861 move(s)
Test #17:
score: 0
Accepted
time: 1ms
memory: 3836kb
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: 661
result:
ok 661 move(s)
Test #18:
score: 0
Accepted
time: 1ms
memory: 3844kb
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: 856
result:
ok 856 move(s)
Test #19:
score: 0
Accepted
time: 1ms
memory: 3840kb
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: 963
result:
ok 963 move(s)
Test #20:
score: 0
Accepted
time: 1ms
memory: 3908kb
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: 1024
result:
ok 1024 move(s)
Test #21:
score: 0
Accepted
time: 1ms
memory: 4136kb
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: 1051
result:
ok 1051 move(s)
Test #22:
score: 0
Accepted
time: 1ms
memory: 3912kb
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: 1042
result:
ok 1042 move(s)
Test #23:
score: 0
Accepted
time: 1ms
memory: 3876kb
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: 613
result:
ok 613 move(s)
Test #24:
score: 0
Accepted
time: 1ms
memory: 4132kb
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: 521
result:
ok 521 move(s)
Test #25:
score: 0
Accepted
time: 1ms
memory: 4140kb
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: 435
result:
ok 435 move(s)
Test #26:
score: 0
Accepted
time: 0ms
memory: 3844kb
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: 329
result:
ok 329 move(s)
Subtask #3:
score: 12
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #27:
score: 12
Accepted
time: 20ms
memory: 4208kb
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: 13174
result:
ok 13174 move(s)
Test #28:
score: 0
Accepted
time: 27ms
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: 19287
result:
ok 19287 move(s)
Test #29:
score: 0
Accepted
time: 24ms
memory: 4020kb
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: 18030
result:
ok 18030 move(s)
Test #30:
score: 0
Accepted
time: 20ms
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: 15030
result:
ok 15030 move(s)
Test #31:
score: 0
Accepted
time: 20ms
memory: 3884kb
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: 15489
result:
ok 15489 move(s)
Test #32:
score: 0
Accepted
time: 36ms
memory: 4080kb
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: 28126
result:
ok 28126 move(s)
Test #33:
score: 0
Accepted
time: 42ms
memory: 4008kb
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: 32092
result:
ok 32092 move(s)
Test #34:
score: 0
Accepted
time: 44ms
memory: 4044kb
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: 34126
result:
ok 34126 move(s)
Test #35:
score: 0
Accepted
time: 10ms
memory: 3832kb
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: 7241
result:
ok 7241 move(s)
Test #36:
score: 0
Accepted
time: 21ms
memory: 3928kb
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: 13767
result:
ok 13767 move(s)
Test #37:
score: 0
Accepted
time: 15ms
memory: 3904kb
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: 4506
result:
ok 4506 move(s)
Test #38:
score: 0
Accepted
time: 14ms
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: 4003
result:
ok 4003 move(s)
Test #39:
score: 0
Accepted
time: 14ms
memory: 4192kb
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: 4127
result:
ok 4127 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: 1104ms
memory: 4588kb
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