제출 #206781

#제출 시각아이디문제언어결과실행 시간메모리
206781NeklixxMeetings (JOI19_meetings)C++14
7 / 100
3068 ms9420 KiB
#include <bits/stdc++.h> #include <meetings.h> #define pb push_back #define mp make_pair #define F first #define S second #define all(v) v.begin(), v.end() #define sh cin.tie(0); cin.sync_with_stdio(0); cout.tie(0); #define FILE freopen("test.in", "r", stdin); #define vprint(v) for (int ii = 0; ii < v.size(); ii++){cout << v[ii] << " ";} #define debugv(v) if (v.size() != 0) {cout << "[ "; for (int __ = 0; __ < (int)(v.size()) - 1; __++){cout << v[__] << ", ";} cout << v[(int)(v.size()) - 1] << " ]" << endl;} else {cout << "[]" << endl;} #define debug cout << "-----------------------------------------------" << endl; #define print1(a) cout << "{ " << a << " }" << endl; #define print2(a, b) cout << "{ " << a << ", " << b << " }" << endl; #define print3(a, b, c) cout << "{ " << a << ", " << b << ", " << c << " }" << endl; #define print4(a, b, c, d) cout << "{ " << a << ", " << b << ", " << c << ", " << d << " }" << endl; using namespace std; //#define int long long const int INF = 1e9 + 228; const int MAXN = 3e3 + 28; map<vector<int>, int> ques; map<pair<int, int>, bool> edges; bool not_leaf[MAXN]; int ask(int x, int y, int z) { vector<int> noww = {x, y, z}; sort(all(noww)); if (ques.count(noww) == 0) { ques[noww] = Query(x, y, z); not_leaf[ques[noww]] = 1; } return ques[noww]; } vector<int> g[MAXN]; int p[MAXN]; int Dsu_get(int x) { if (p[x] == x) { return x; } return p[x] = Dsu_get(p[x]); } void Dsu_Unique(int x, int y) { x = Dsu_get(x); y = Dsu_get(y); if (x != y) p[x] = y; } void Solve(int n) { for (int i = 0; i < n; i++) { p[i] = i; } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int _ = j + 1; _ < n; _++) { ask(i, j, _); } } } vector<int> level; for (int i = 0; i < n; i++) { if (!not_leaf[i]) level.pb(i); } while (!level.empty()) { vector<int> tmp; sort(all(level)); level.erase(unique(all(level)), level.end()); //print1("new_level"); for (auto i : level) { //print1(i + 1); pair<int, int> res = mp(-1, -1); for (int candidate = 0; candidate < n; candidate++) { if (candidate == i || Dsu_get(candidate) == Dsu_get(i)) continue; int cnt = 0; for (int j = 0; j < n; j++) { if (j == i || j == candidate || Dsu_get(j) == Dsu_get(i)) continue; if (ask(candidate, i, j) == candidate) { cnt++; } } res = max(res, mp(cnt, candidate)); } if (res.S == -1) continue; g[i].pb(res.S); g[res.S].pb(i); tmp.pb(res.S); //print2(i + 1, res.S + 1); Dsu_Unique(i, res.S); } level = tmp; } for (int i = 0; i < n; i++) { for (auto to : g[i]) { if (!edges[mp(i, to)] && !edges[mp(to, i)]) { edges[mp(i, to)] = edges[mp(to, i)] = 1; Bridge(i, to); } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...