#include "meetings.h"
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
map<int, vector<int>> mapchik;
vector<int> path;
void Answer(int u, int v) {
Bridge(min(u, v), max(u, v));
}
void solve(vector<int> v) {
if (v.size() < 2) return;
shuffle(all(v), rng);
int x = v[0], y = v[1];
path.clear();
mapchik[x].pb(x);
mapchik[y].pb(y);
for (int i = 2; i < v.size(); i++) {
int p = Query(x, y, v[i]);
if (mapchik[p].empty())
path.pb(p);
mapchik[p].pb(v[i]);
}
sort(all(path), [&](int i, int j) {
return Query(x, i, j) == i;
});
int prv = x;
for (int i = 0; i < path.size(); i++)
Answer(prv, path[i]), prv = path[i];
Answer(prv, y);
vector<vector<int>> todo;
for (auto it : mapchik)
todo.pb(it.se);
mapchik[x].clear();
mapchik[y].clear();
for (int i = 0; i < path.size(); i++)
mapchik[path[i]].clear();
for (auto it : todo)
solve(it);
}
void Solve(int n) {
vector<int> vec;
for (int i = 0; i < n; i++)
vec.pb(i);
solve(vec);
}
Compilation message
meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i = 2; i < v.size(); i++) {
| ~~^~~~~~~~~~
meetings.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < path.size(); i++)
| ~~^~~~~~~~~~~~~
meetings.cpp:87:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int i = 0; i < path.size(); i++)
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Correct |
0 ms |
336 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
0 ms |
336 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
0 ms |
336 KB |
Output is correct |
11 |
Correct |
0 ms |
336 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
0 ms |
336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Correct |
0 ms |
336 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
0 ms |
336 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
0 ms |
336 KB |
Output is correct |
11 |
Correct |
0 ms |
336 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
0 ms |
336 KB |
Output is correct |
14 |
Correct |
1 ms |
336 KB |
Output is correct |
15 |
Correct |
1 ms |
336 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
1 ms |
336 KB |
Output is correct |
21 |
Correct |
1 ms |
336 KB |
Output is correct |
22 |
Correct |
1 ms |
336 KB |
Output is correct |
23 |
Correct |
1 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
336 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
0 ms |
336 KB |
Output is correct |
4 |
Correct |
0 ms |
336 KB |
Output is correct |
5 |
Correct |
0 ms |
336 KB |
Output is correct |
6 |
Correct |
0 ms |
336 KB |
Output is correct |
7 |
Correct |
0 ms |
336 KB |
Output is correct |
8 |
Correct |
0 ms |
336 KB |
Output is correct |
9 |
Correct |
0 ms |
336 KB |
Output is correct |
10 |
Correct |
0 ms |
336 KB |
Output is correct |
11 |
Correct |
0 ms |
336 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
0 ms |
336 KB |
Output is correct |
14 |
Correct |
1 ms |
336 KB |
Output is correct |
15 |
Correct |
1 ms |
336 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
1 ms |
336 KB |
Output is correct |
20 |
Correct |
1 ms |
336 KB |
Output is correct |
21 |
Correct |
1 ms |
336 KB |
Output is correct |
22 |
Correct |
1 ms |
336 KB |
Output is correct |
23 |
Correct |
1 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
336 KB |
Output is correct |
25 |
Correct |
1 ms |
336 KB |
Output is correct |
26 |
Correct |
1 ms |
336 KB |
Output is correct |
27 |
Correct |
5 ms |
476 KB |
Output is correct |
28 |
Correct |
4 ms |
464 KB |
Output is correct |
29 |
Correct |
5 ms |
464 KB |
Output is correct |
30 |
Correct |
5 ms |
548 KB |
Output is correct |
31 |
Correct |
5 ms |
464 KB |
Output is correct |
32 |
Correct |
7 ms |
464 KB |
Output is correct |
33 |
Correct |
8 ms |
592 KB |
Output is correct |
34 |
Correct |
10 ms |
464 KB |
Output is correct |
35 |
Correct |
8 ms |
464 KB |
Output is correct |
36 |
Correct |
5 ms |
516 KB |
Output is correct |
37 |
Correct |
8 ms |
464 KB |
Output is correct |
38 |
Correct |
8 ms |
464 KB |
Output is correct |
39 |
Correct |
8 ms |
520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
335 ms |
1392 KB |
Output is correct |
2 |
Correct |
385 ms |
1656 KB |
Output is correct |
3 |
Correct |
395 ms |
1504 KB |
Output is correct |
4 |
Correct |
354 ms |
1400 KB |
Output is correct |
5 |
Correct |
275 ms |
1244 KB |
Output is correct |
6 |
Correct |
296 ms |
1416 KB |
Output is correct |
7 |
Correct |
379 ms |
1640 KB |
Output is correct |
8 |
Correct |
390 ms |
1764 KB |
Output is correct |
9 |
Correct |
386 ms |
1908 KB |
Output is correct |
10 |
Correct |
365 ms |
2032 KB |
Output is correct |
11 |
Correct |
425 ms |
1848 KB |
Output is correct |
12 |
Correct |
375 ms |
1460 KB |
Output is correct |
13 |
Correct |
279 ms |
1560 KB |
Output is correct |
14 |
Correct |
355 ms |
1796 KB |
Output is correct |
15 |
Correct |
310 ms |
1536 KB |
Output is correct |
16 |
Correct |
312 ms |
1476 KB |
Output is correct |
17 |
Correct |
390 ms |
1816 KB |
Output is correct |
18 |
Correct |
315 ms |
1772 KB |
Output is correct |
19 |
Correct |
340 ms |
1796 KB |
Output is correct |
20 |
Correct |
448 ms |
1792 KB |
Output is correct |
21 |
Correct |
335 ms |
1396 KB |
Output is correct |
22 |
Correct |
340 ms |
1512 KB |
Output is correct |
23 |
Correct |
322 ms |
1580 KB |
Output is correct |
24 |
Correct |
333 ms |
1508 KB |
Output is correct |
25 |
Correct |
411 ms |
1740 KB |
Output is correct |
26 |
Correct |
314 ms |
1688 KB |
Output is correct |
27 |
Correct |
368 ms |
1636 KB |
Output is correct |
28 |
Correct |
405 ms |
1812 KB |
Output is correct |
29 |
Correct |
359 ms |
1776 KB |
Output is correct |
30 |
Correct |
388 ms |
1760 KB |
Output is correct |
31 |
Correct |
393 ms |
2176 KB |
Output is correct |
32 |
Correct |
675 ms |
1504 KB |
Output is correct |
33 |
Correct |
646 ms |
1436 KB |
Output is correct |
34 |
Correct |
5 ms |
464 KB |
Output is correct |
35 |
Correct |
4 ms |
464 KB |
Output is correct |
36 |
Correct |
5 ms |
464 KB |
Output is correct |
37 |
Correct |
4 ms |
464 KB |
Output is correct |
38 |
Correct |
5 ms |
464 KB |
Output is correct |
39 |
Correct |
6 ms |
544 KB |
Output is correct |
40 |
Correct |
8 ms |
464 KB |
Output is correct |
41 |
Correct |
8 ms |
548 KB |
Output is correct |
42 |
Correct |
8 ms |
464 KB |
Output is correct |
43 |
Correct |
5 ms |
464 KB |
Output is correct |
44 |
Correct |
9 ms |
464 KB |
Output is correct |
45 |
Correct |
8 ms |
464 KB |
Output is correct |
46 |
Correct |
9 ms |
464 KB |
Output is correct |
47 |
Correct |
1 ms |
336 KB |
Output is correct |
48 |
Correct |
1 ms |
336 KB |
Output is correct |
49 |
Correct |
1 ms |
336 KB |
Output is correct |
50 |
Correct |
1 ms |
336 KB |
Output is correct |
51 |
Correct |
1 ms |
336 KB |
Output is correct |
52 |
Correct |
1 ms |
336 KB |
Output is correct |
53 |
Correct |
1 ms |
336 KB |
Output is correct |
54 |
Correct |
1 ms |
336 KB |
Output is correct |
55 |
Correct |
1 ms |
336 KB |
Output is correct |
56 |
Correct |
1 ms |
336 KB |
Output is correct |
57 |
Correct |
1 ms |
336 KB |
Output is correct |
58 |
Correct |
1 ms |
336 KB |
Output is correct |
59 |
Correct |
1 ms |
336 KB |
Output is correct |
60 |
Correct |
0 ms |
336 KB |
Output is correct |
61 |
Correct |
0 ms |
336 KB |
Output is correct |
62 |
Correct |
0 ms |
336 KB |
Output is correct |
63 |
Correct |
0 ms |
336 KB |
Output is correct |
64 |
Correct |
0 ms |
336 KB |
Output is correct |
65 |
Correct |
0 ms |
336 KB |
Output is correct |
66 |
Correct |
0 ms |
336 KB |
Output is correct |
67 |
Correct |
0 ms |
336 KB |
Output is correct |
68 |
Correct |
1 ms |
336 KB |
Output is correct |
69 |
Correct |
0 ms |
336 KB |
Output is correct |
70 |
Correct |
0 ms |
336 KB |
Output is correct |
71 |
Correct |
0 ms |
336 KB |
Output is correct |
72 |
Correct |
0 ms |
336 KB |
Output is correct |