#include "meetings.h"
#include <vector>
#include <map>
#include <ctime>
#include <iostream>
#include <algorithm>
using namespace std;
// 同じコードを提出して,https://oj.uz/submission/206974 では 100 点取れているんですけど,
// ひどい仕打ちをやめてくれ!
// おい,なめてんのか,grader の Query 関数は LCA で O(log N) で実装できるのに,なんで実装サボってんだ!!!!!!
vector<int> G[2009];
vector<int> I, J1, J2;
int ret1, ret2, ret3, ret4, allret;
bool passed[2009];
bool forced[2009];
map<pair<int, int>, int> Map[2009];
int Ask(int u, int v, int w) {
int x[3] = { u, v, w };
sort(x, x + 3);
if (Map[x[0]][make_pair(x[1], x[2])] >= 1) return Map[x[0]][make_pair(x[1], x[2])] - 1;
int Z = Query(x[0], x[1], x[2]);
Map[x[0]][make_pair(x[1], x[2])] = Z + 1;
return Z;
}
void dfs(int pos) {
passed[pos] = true; int cnts = 0;
for (int i = 0; i < G[pos].size(); i++) {
if (passed[G[pos][i]] == true) continue;
dfs(G[pos][i]); cnts++;
}
if (cnts == 0) I.push_back(pos);
}
void dfs2(int pos, int to) {
if (pos == to) { J2 = J1; return; }
passed[pos] = true;
for (int i = 0; i < G[pos].size(); i++) {
if (passed[G[pos][i]] == true) continue;
J1.push_back(G[pos][i]);
dfs2(G[pos][i], to);
J1.pop_back();
}
}
vector<int> getpath(int u, int v) {
J1.clear(); J2.clear();
J1.push_back(u);
dfs2(u, v);
return J2;
}
int getlca(int root, vector<pair<int, int>> E) {
vector<int> cand; I.clear();
for (int i = 0; i < E.size(); i++) cand.push_back(E[i].first);
for (int i = 0; i < E.size(); i++) cand.push_back(E[i].second);
for (int i : cand) G[i].clear();
for (int i : cand) passed[i] = false;
for (int i : cand) forced[i] = false;
for (int i = 0; i < E.size(); i++) {
G[E[i].first].push_back(E[i].second);
G[E[i].second].push_back(E[i].first);
}
dfs(E[0].first);
if (G[E[0].first].size() == 1) I.push_back(E[0].first);
int mi = I.size() / 2;
for (int i = mi; i < I.size(); i++) {
int R = Ask(root, I[i - mi], I[i]); ret3++;
for (int j : cand) passed[j] = false;
vector<int> C1 = getpath(I[i - mi], R);
for (int j = 0; j < C1.size() - 1; j++) forced[C1[j]] = true;
for (int j : cand) passed[j] = false;
vector<int> C2 = getpath(I[i], R);
for (int j = 0; j < C2.size() - 1; j++) forced[C2[j]] = true;
}
for (int i : cand) {
if (forced[i] == false) return i;
}
return -1;
}
vector<pair<int, int>> dfs(vector<int> A) {
if (A.size() == 1) {
return vector<pair<int, int>>{};
}
else if (A.size() == 2) {
return vector<pair<int, int>>{make_pair(A[0], A[1])};
}
else if (A.size() == 3) {
ret4++;
int R = Ask(A[0], A[1], A[2]);
vector<pair<int, int>> E;
for (int i : A) { if (i != R) E.push_back(make_pair(i, R)); }
return E;
}
else if (A.size() == 4) {
vector<int> G1[24], G2[24];
for (int i = 1; i < A.size(); i++) {
for (int j = i + 1; j < A.size(); j++) {
int V = Ask(A[0], A[i], A[j]); ret4++;
if (V == A[i]) { G1[i].push_back(j); G2[j].push_back(i); }
if (V == A[j]) { G1[j].push_back(i); G2[i].push_back(j); }
}
}
vector<int> dist(24, 0);
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < A.size(); j++) {
for (int k : G1[j]) dist[k] = max(dist[k], dist[j] + 1);
}
}
vector<pair<int, int>> E;
for (int i = 1; i < A.size(); i++) {
int s = 0;
for (int j : G2[i]) {
if (dist[j] == dist[i] - 1) s = j;
}
E.push_back(make_pair(A[i], A[s]));
}
return E;
}
else {
allret += A.size();
//cout << allret << " " << A.size() << endl;
}
// 重心っぽい頂点を見つける
int grav = -1;
while (true) {
int s = rand() % A.size(), cnt = 0; bool flag = false;
int maxlim = 0;
if (A.size() <= 7) maxlim = 0;
else if (A.size() <= 20) maxlim = 3;
else if (A.size() <= 50) maxlim = 6;
else if (A.size() <= 200) maxlim = 9;
else if (A.size() <= 500) maxlim = 13;
else if (A.size() <= 1000) maxlim = 24;
else if (A.size() <= 2000) maxlim = 37;
for (int i = 1; i <= maxlim; i++) {
int t = -1, u = -1;
while (A[s] == t || t == u || A[s] == u) {
t = A[rand() % A.size()];
u = A[rand() % A.size()];
}
ret1++;
if (Ask(A[s], t, u) == A[s]) cnt++;
if (i == 1 && cnt <= 0) { flag = true; break; }
if (i == 3 && cnt <= 1) { flag = true; break; }
if (i == 6 && cnt <= 2) { flag = true; break; }
if (i == 9 && cnt <= 3) { flag = true; break; }
if (i == 13 && cnt <= 4) { flag = true; break; }
if (i == 16 && cnt <= 5) { flag = true; break; }
if (i == 20 && cnt <= 6) { flag = true; break; }
if (i == 24 && cnt <= 7) { flag = true; break; }
if (i == 28 && cnt <= 8) { flag = true; break; }
if (i == 32 && cnt <= 9) { flag = true; break; }
if (i == 37 && cnt <= 10) { flag = true; break; }
}
if (flag == false) { grav = s; break; }
}
//cout << A.size() << " " << ret1 << endl;
// 重心分解をする
vector<int> cand;
for (int i = 0; i < A.size(); i++) { if (i != grav) cand.push_back(i); }
for (int i = 0; i < A.size() * 20; i++) swap(cand[rand() % cand.size()], cand[rand() % cand.size()]);
vector<vector<int>> centroid;
for (int i : cand) {
vector<pair<int, int>> Z;
for (int j = 0; j < centroid.size(); j++) Z.push_back(make_pair(centroid[j].size(), j));
sort(Z.begin(), Z.end());
bool flag = false;
for (int j = Z.size() - 1; j >= 0; j--) {
int num = Z[j].second;
int root = centroid[num][0];
int V = Ask(A[grav], A[i], root); ret2++;
if (V != A[grav]) { centroid[num].push_back(A[i]); flag = true; break; }
}
if (flag == false) centroid.push_back(vector<int>{A[i]});
}
// 復元をする
vector<pair<int, int>> ans;
for (vector<int> f : centroid) {
vector<pair<int, int>> Z = dfs(f);
for (pair<int, int> i : Z) ans.push_back(i);
int U = f[0];
if (Z.size() >= 1) U = getlca(A[grav], Z);
ans.push_back(make_pair(A[grav], U));
}
return ans;
}
void Solve(int N) {
vector<int> L;
for (int i = 0; i < N; i++) L.push_back(i);
vector<pair<int, int>> V = dfs(L);
for (int i = 0; i < V.size(); i++) {
if (V[i].first > V[i].second) swap(V[i].first, V[i].second);
Bridge(V[i].first, V[i].second);
}
return;
}
Compilation message
meetings.cpp: In function 'void dfs(int)':
meetings.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
meetings.cpp: In function 'void dfs2(int, int)':
meetings.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < G[pos].size(); i++) {
~~^~~~~~~~~~~~~~~
meetings.cpp: In function 'int getlca(int, std::vector<std::pair<int, int> >)':
meetings.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E.size(); i++) cand.push_back(E[i].first);
~~^~~~~~~~~~
meetings.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E.size(); i++) cand.push_back(E[i].second);
~~^~~~~~~~~~
meetings.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < E.size(); i++) {
~~^~~~~~~~~~
meetings.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = mi; i < I.size(); i++) {
~~^~~~~~~~~~
meetings.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < C1.size() - 1; j++) forced[C1[j]] = true;
~~^~~~~~~~~~~~~~~
meetings.cpp:79:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < C2.size() - 1; j++) forced[C2[j]] = true;
~~^~~~~~~~~~~~~~~
meetings.cpp: In function 'std::vector<std::pair<int, int> > dfs(std::vector<int>)':
meetings.cpp:104:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < A.size(); i++) {
~~^~~~~~~~~~
meetings.cpp:105:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = i + 1; j < A.size(); j++) {
~~^~~~~~~~~~
meetings.cpp:112:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < A.size(); i++) {
~~^~~~~~~~~~
meetings.cpp:113:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < A.size(); j++) {
~~^~~~~~~~~~
meetings.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < A.size(); i++) {
~~^~~~~~~~~~
meetings.cpp:170:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < A.size(); i++) { if (i != grav) cand.push_back(i); }
~~^~~~~~~~~~
meetings.cpp:171:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < A.size() * 20; i++) swap(cand[rand() % cand.size()], cand[rand() % cand.size()]);
~~^~~~~~~~~~~~~~~
meetings.cpp:176:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < centroid.size(); j++) Z.push_back(make_pair(centroid[j].size(), j));
~~^~~~~~~~~~~~~~~~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:207:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < V.size(); i++) {
~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
508 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
4 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
504 KB |
Output is correct |
12 |
Correct |
5 ms |
508 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
508 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
4 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
504 KB |
Output is correct |
12 |
Correct |
5 ms |
508 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
14 |
Correct |
6 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
504 KB |
Output is correct |
16 |
Correct |
5 ms |
508 KB |
Output is correct |
17 |
Correct |
5 ms |
504 KB |
Output is correct |
18 |
Correct |
5 ms |
504 KB |
Output is correct |
19 |
Correct |
5 ms |
504 KB |
Output is correct |
20 |
Correct |
6 ms |
504 KB |
Output is correct |
21 |
Correct |
5 ms |
504 KB |
Output is correct |
22 |
Correct |
5 ms |
504 KB |
Output is correct |
23 |
Correct |
5 ms |
504 KB |
Output is correct |
24 |
Correct |
5 ms |
504 KB |
Output is correct |
25 |
Correct |
5 ms |
504 KB |
Output is correct |
26 |
Correct |
5 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
504 KB |
Output is correct |
3 |
Correct |
5 ms |
508 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
504 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
504 KB |
Output is correct |
10 |
Correct |
4 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
504 KB |
Output is correct |
12 |
Correct |
5 ms |
508 KB |
Output is correct |
13 |
Correct |
4 ms |
504 KB |
Output is correct |
14 |
Correct |
6 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
504 KB |
Output is correct |
16 |
Correct |
5 ms |
508 KB |
Output is correct |
17 |
Correct |
5 ms |
504 KB |
Output is correct |
18 |
Correct |
5 ms |
504 KB |
Output is correct |
19 |
Correct |
5 ms |
504 KB |
Output is correct |
20 |
Correct |
6 ms |
504 KB |
Output is correct |
21 |
Correct |
5 ms |
504 KB |
Output is correct |
22 |
Correct |
5 ms |
504 KB |
Output is correct |
23 |
Correct |
5 ms |
504 KB |
Output is correct |
24 |
Correct |
5 ms |
504 KB |
Output is correct |
25 |
Correct |
5 ms |
504 KB |
Output is correct |
26 |
Correct |
5 ms |
504 KB |
Output is correct |
27 |
Correct |
17 ms |
760 KB |
Output is correct |
28 |
Correct |
20 ms |
760 KB |
Output is correct |
29 |
Correct |
18 ms |
760 KB |
Output is correct |
30 |
Correct |
19 ms |
760 KB |
Output is correct |
31 |
Correct |
19 ms |
764 KB |
Output is correct |
32 |
Correct |
19 ms |
764 KB |
Output is correct |
33 |
Correct |
19 ms |
764 KB |
Output is correct |
34 |
Correct |
21 ms |
888 KB |
Output is correct |
35 |
Correct |
25 ms |
888 KB |
Output is correct |
36 |
Correct |
19 ms |
760 KB |
Output is correct |
37 |
Correct |
19 ms |
760 KB |
Output is correct |
38 |
Correct |
20 ms |
760 KB |
Output is correct |
39 |
Correct |
18 ms |
760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
960 ms |
2808 KB |
Output is correct |
2 |
Correct |
796 ms |
2808 KB |
Output is correct |
3 |
Correct |
1180 ms |
3192 KB |
Output is correct |
4 |
Correct |
975 ms |
2820 KB |
Output is correct |
5 |
Correct |
1111 ms |
3120 KB |
Output is correct |
6 |
Correct |
847 ms |
3076 KB |
Output is correct |
7 |
Correct |
845 ms |
3644 KB |
Output is correct |
8 |
Correct |
879 ms |
3948 KB |
Output is correct |
9 |
Correct |
866 ms |
3940 KB |
Output is correct |
10 |
Correct |
718 ms |
4088 KB |
Output is correct |
11 |
Correct |
812 ms |
3868 KB |
Output is correct |
12 |
Correct |
1179 ms |
3212 KB |
Output is correct |
13 |
Correct |
1089 ms |
3320 KB |
Output is correct |
14 |
Correct |
888 ms |
3448 KB |
Output is correct |
15 |
Correct |
871 ms |
3448 KB |
Output is correct |
16 |
Correct |
836 ms |
3452 KB |
Output is correct |
17 |
Correct |
1020 ms |
4088 KB |
Output is correct |
18 |
Correct |
955 ms |
3448 KB |
Output is correct |
19 |
Correct |
1064 ms |
3472 KB |
Output is correct |
20 |
Correct |
937 ms |
3448 KB |
Output is correct |
21 |
Correct |
1038 ms |
3704 KB |
Output is correct |
22 |
Correct |
1076 ms |
3320 KB |
Output is correct |
23 |
Correct |
1087 ms |
3448 KB |
Output is correct |
24 |
Correct |
1025 ms |
3448 KB |
Output is correct |
25 |
Correct |
1064 ms |
3400 KB |
Output is correct |
26 |
Correct |
1109 ms |
3448 KB |
Output is correct |
27 |
Correct |
1207 ms |
3448 KB |
Output is correct |
28 |
Correct |
880 ms |
3960 KB |
Output is correct |
29 |
Correct |
650 ms |
3704 KB |
Output is correct |
30 |
Correct |
865 ms |
4104 KB |
Output is correct |
31 |
Correct |
720 ms |
3832 KB |
Output is correct |
32 |
Correct |
1041 ms |
2936 KB |
Output is correct |
33 |
Correct |
812 ms |
2884 KB |
Output is correct |
34 |
Correct |
17 ms |
636 KB |
Output is correct |
35 |
Correct |
20 ms |
760 KB |
Output is correct |
36 |
Correct |
18 ms |
760 KB |
Output is correct |
37 |
Correct |
19 ms |
760 KB |
Output is correct |
38 |
Correct |
21 ms |
760 KB |
Output is correct |
39 |
Correct |
19 ms |
888 KB |
Output is correct |
40 |
Correct |
20 ms |
760 KB |
Output is correct |
41 |
Correct |
20 ms |
888 KB |
Output is correct |
42 |
Correct |
25 ms |
888 KB |
Output is correct |
43 |
Correct |
21 ms |
760 KB |
Output is correct |
44 |
Correct |
21 ms |
760 KB |
Output is correct |
45 |
Correct |
20 ms |
760 KB |
Output is correct |
46 |
Correct |
19 ms |
760 KB |
Output is correct |
47 |
Correct |
5 ms |
632 KB |
Output is correct |
48 |
Correct |
6 ms |
504 KB |
Output is correct |
49 |
Correct |
5 ms |
504 KB |
Output is correct |
50 |
Correct |
5 ms |
504 KB |
Output is correct |
51 |
Correct |
5 ms |
504 KB |
Output is correct |
52 |
Correct |
5 ms |
508 KB |
Output is correct |
53 |
Correct |
5 ms |
632 KB |
Output is correct |
54 |
Correct |
5 ms |
504 KB |
Output is correct |
55 |
Correct |
5 ms |
508 KB |
Output is correct |
56 |
Correct |
5 ms |
632 KB |
Output is correct |
57 |
Correct |
6 ms |
632 KB |
Output is correct |
58 |
Correct |
5 ms |
504 KB |
Output is correct |
59 |
Correct |
5 ms |
504 KB |
Output is correct |
60 |
Correct |
5 ms |
504 KB |
Output is correct |
61 |
Correct |
6 ms |
504 KB |
Output is correct |
62 |
Correct |
5 ms |
504 KB |
Output is correct |
63 |
Correct |
5 ms |
504 KB |
Output is correct |
64 |
Correct |
5 ms |
504 KB |
Output is correct |
65 |
Correct |
5 ms |
504 KB |
Output is correct |
66 |
Correct |
5 ms |
504 KB |
Output is correct |
67 |
Correct |
5 ms |
504 KB |
Output is correct |
68 |
Correct |
5 ms |
504 KB |
Output is correct |
69 |
Correct |
5 ms |
504 KB |
Output is correct |
70 |
Correct |
5 ms |
504 KB |
Output is correct |
71 |
Correct |
5 ms |
504 KB |
Output is correct |
72 |
Correct |
5 ms |
504 KB |
Output is correct |