제출 #1082115

#제출 시각아이디문제언어결과실행 시간메모리
1082115Boas가장 긴 여행 (IOI23_longesttrip)C++17
15 / 100
943 ms5776 KiB
#include "longesttrip.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <typename T1, typename T2> using indexed_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>; template <typename T> using indexed_set = indexed_map<T, null_type>; #define loop(x, i) for (int i = 0; i < (x); i++) #define loop1(x, i) for (int i = 1; i <= (x); i++) #define rev(x, i) for (int i = (int)(x) - 1; i >= 0; i--) #define itloop(x) for (auto it = begin(x); x != end(x); it++) #define itrev(x) for (auto it = rbegin(x); x != rend(x); it++) #define INF32 ((int32_t)(2e9 + 1)) #define ALL(x) begin(x), end(x) #define RALL(x) rbegin(x), rend(x) #define removeIn(x, l) l.erase(find(ALL(l), x)) #define pb push_back #define sz(x) (int)(x).size() #define F first #define S second #define var const auto & #define foreach(l) for (var e : l) typedef int8_t i8; typedef int16_t i16; typedef int32_t i32; typedef int64_t i64; typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef tuple<int, int, int, int> iiii; typedef vector<int> vi; typedef vector<i32> vi32; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<vi32> vvi32; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<vii> vvii; typedef vector<viii> vviii; typedef set<int> si; typedef set<ii> sii; typedef set<iii> siii; typedef vector<si> vsi; typedef vector<sii> vsii; typedef vector<vsi> vvsi; typedef vector<string> vstr; typedef vector<vector<string>> vvstr; typedef vector<bool> vb; typedef vector<vb> vvb; vi longest_trip(int N, int D) { if (D >= 2) { vi res(N); iota(ALL(res), 0); if (D == 3) { return res; } si resterend; loop1(N - 1, i) resterend.insert(res[i]); loop1(N - 1, i) { auto it = resterend.begin(); if (are_connected({res[i - 1]}, {*it})) { res[i] = *it; resterend.erase(it); } else { if (resterend.size() == 1) { res.insert(res.begin(), *it); res.pop_back(); return res; } res[i] = *next(it); resterend.erase(next(it)); } } return res; } else { vsi adj(N); for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if (are_connected({i}, {j})) { adj[i].insert(j); adj[j].insert(i); } } } if (N <= 4) { vb vis(N); ii furthest; vi route; vi bestRoute; auto dfs = [&](auto &&self, int i, int d) -> ii { ii maxD = {d, i}; if (maxD > furthest) { furthest = max(furthest, maxD); } vis[i] = 1; for (int j : adj[i]) { if (!vis[j]) maxD = max(maxD, self(self, j, d + 1)); } if (maxD == furthest) { route.pb(i); if (sz(route) > sz(bestRoute)) bestRoute = route; } return maxD; }; loop(N, i) { vis = vb(N); route.clear(); dfs(dfs, i, 0); } return bestRoute; } si clique1, clique2; loop(N, i) { for (int j = i + 1; j < N; j++) { if (adj[i].count(j)) continue; if (clique1.empty()) { clique1.insert(i); clique2.insert(j); } else { bool iVal2 = 1, iVal1 = 1, jVal2 = 1, jVal1 = 1; for (int k : clique1) { if (adj[i].count(k)) { iVal2 = 0; } else { iVal1 = 0; } if (adj[j].count(k)) { jVal2 = 0; } else { jVal1 = 0; } } for (int k : clique2) { if (adj[i].count(k)) { iVal1 = 0; } else { iVal2 = 0; } if (adj[j].count(k)) { jVal1 = 0; } else { jVal2 = 0; } } if (iVal1 || jVal2) { clique1.insert(i); clique2.insert(j); } else if (iVal2 || jVal1) { clique2.insert(i); clique1.insert(j); } } } } loop(N, i) { if (clique1.count(i) || clique2.count(i)) continue; bool iVal2 = 1, iVal1 = 1; for (int k : clique1) { if (!adj[i].count(k)) { iVal1 = 0; } } for (int k : clique2) { if (!adj[i].count(k)) { iVal2 = 0; } } if (iVal1) { clique1.insert(i); } else if (iVal2) { clique2.insert(i); } else throw; } ii bridge = {-1, -1}; for (int i : clique1) { for (int j : adj[i]) { if (clique2.count(j)) { bridge = {i, j}; break; } } } assert(sz(clique1) + sz(clique2) == N); vi res; if (bridge.F == -1) { if (sz(clique1) < sz(clique2)) { swap(clique1, clique2); } for (int i : clique1) res.pb(i); return res; } for (int i : clique1) { if (i != bridge.F) res.pb(i); } res.pb(bridge.F); res.pb(bridge.S); for (int i : clique2) { if (i != bridge.S) res.pb(i); } return res; } throw; return {}; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...