#include "meetings.h"
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
vector<pair<int, int>> T;
vector<int> random_shuffle(vector<int> I) {
for (int i = 0; i < I.size(); i++) swap(I[rand() % I.size()], I[rand() % I.size()]);
return I;
}
void dfs(vector<int> vec) {
// サイズが 1, 2, 3 のときに場合分け
if (vec.size() == 1) return;
if (vec.size() == 2) {
T.push_back(make_pair(vec[0], vec[1]));
return;
}
if (vec.size() == 3) {
int S = Query(vec[0], vec[1], vec[2]);
if (vec[0] != S) T.push_back(make_pair(vec[0], S));
if (vec[1] != S) T.push_back(make_pair(vec[1], S));
if (vec[2] != S) T.push_back(make_pair(vec[2], S));
return;
}
vec = random_shuffle(vec);
while (true) {
// 乱択アルゴリズムで重心を見つける
int v = vec[rand() % vec.size()], cnt = 0;
for (int t = 0; t < 8; t++) {
int v1 = v, v2 = v;
while (v1 == v2 || v1 == v || v2 == v) {
v1 = vec[rand() % vec.size()];
v2 = vec[rand() % vec.size()];
}
int S = Query(v, v1, v2);
if (S == v) cnt++;
}
if (cnt <= 2) continue;
// 連結成分ごとに分ける
vector<int>col(vec.size(), -1); int cnts = 0;
for (int t = 0; t < vec.size(); t++) {
if (col[t] >= 0 || vec[t] == v) continue;
cnts++; col[t] = cnts;
for (int j = 0; j < vec.size(); j++) {
if (col[j] >= 0 || vec[j] == v) continue;
int S = Query(v, vec[t], vec[j]);
if (S != v) { col[j] = cnts; }
}
}
for (int t = 1; t <= cnts; t++) {
vector<int>E;
for (int j = 0; j < vec.size(); j++) {
if (col[j] == t) E.push_back(vec[j]);
}
int cur = E[0];
for (int j = 1; j < E.size(); j++) {
int F = Query(v, cur, E[j]);
if (F == E[j]) cur = E[j];
}
T.push_back(make_pair(v, cur));
dfs(E);
}
break;
}
}
void Solve(int N) {
srand((unsigned)time(NULL));
vector<int> vec;
for (int i = 0; i < N; i++) vec.push_back(i);
dfs(vec);
for (int i = 0; i < T.size(); i++) {
if (T[i].first > T[i].second) swap(T[i].first, T[i].second);
Bridge(T[i].first, T[i].second);
}
return;
}
Compilation message
meetings.cpp: In function 'std::vector<int> random_shuffle(std::vector<int>)':
meetings.cpp:10:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < I.size(); i++) swap(I[rand() % I.size()], I[rand() % I.size()]);
~~^~~~~~~~~~
meetings.cpp: In function 'void dfs(std::vector<int>)':
meetings.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int t = 0; t < vec.size(); t++) {
~~^~~~~~~~~~~~
meetings.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++) {
~~^~~~~~~~~~~~
meetings.cpp:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j++) {
~~^~~~~~~~~~~~
meetings.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < E.size(); j++) {
~~^~~~~~~~~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < T.size(); i++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
248 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
248 KB |
Output is correct |
| 6 |
Correct |
2 ms |
248 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
248 KB |
Output is correct |
| 10 |
Correct |
3 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
248 KB |
Output is correct |
| 13 |
Correct |
2 ms |
380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
248 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
248 KB |
Output is correct |
| 6 |
Correct |
2 ms |
248 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
248 KB |
Output is correct |
| 10 |
Correct |
3 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
248 KB |
Output is correct |
| 13 |
Correct |
2 ms |
380 KB |
Output is correct |
| 14 |
Correct |
2 ms |
248 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
248 KB |
Output is correct |
| 17 |
Correct |
3 ms |
376 KB |
Output is correct |
| 18 |
Correct |
3 ms |
376 KB |
Output is correct |
| 19 |
Correct |
3 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
248 KB |
Output is correct |
| 21 |
Correct |
3 ms |
252 KB |
Output is correct |
| 22 |
Correct |
3 ms |
376 KB |
Output is correct |
| 23 |
Correct |
4 ms |
380 KB |
Output is correct |
| 24 |
Correct |
2 ms |
376 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
248 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
248 KB |
Output is correct |
| 6 |
Correct |
2 ms |
248 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
248 KB |
Output is correct |
| 10 |
Correct |
3 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
248 KB |
Output is correct |
| 13 |
Correct |
2 ms |
380 KB |
Output is correct |
| 14 |
Correct |
2 ms |
248 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
248 KB |
Output is correct |
| 17 |
Correct |
3 ms |
376 KB |
Output is correct |
| 18 |
Correct |
3 ms |
376 KB |
Output is correct |
| 19 |
Correct |
3 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
248 KB |
Output is correct |
| 21 |
Correct |
3 ms |
252 KB |
Output is correct |
| 22 |
Correct |
3 ms |
376 KB |
Output is correct |
| 23 |
Correct |
4 ms |
380 KB |
Output is correct |
| 24 |
Correct |
2 ms |
376 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
| 26 |
Correct |
2 ms |
248 KB |
Output is correct |
| 27 |
Correct |
21 ms |
376 KB |
Output is correct |
| 28 |
Correct |
19 ms |
376 KB |
Output is correct |
| 29 |
Correct |
23 ms |
376 KB |
Output is correct |
| 30 |
Correct |
21 ms |
376 KB |
Output is correct |
| 31 |
Correct |
21 ms |
392 KB |
Output is correct |
| 32 |
Correct |
39 ms |
376 KB |
Output is correct |
| 33 |
Correct |
32 ms |
376 KB |
Output is correct |
| 34 |
Correct |
28 ms |
632 KB |
Output is correct |
| 35 |
Correct |
28 ms |
376 KB |
Output is correct |
| 36 |
Correct |
22 ms |
376 KB |
Output is correct |
| 37 |
Correct |
20 ms |
376 KB |
Output is correct |
| 38 |
Correct |
23 ms |
376 KB |
Output is correct |
| 39 |
Correct |
22 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3026 ms |
828 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
