Submission #1238399

#TimeUsernameProblemLanguageResultExecution timeMemory
1238399VahanAbrahamLongest Trip (IOI23_longesttrip)C++20
40 / 100
367 ms12476 KiB
#define _CRT_SECURE_NO_WARNINGS #include "longesttrip.h" #include <iostream> #include <string> #include <algorithm> #include <cstring> #include <cstdio> #include <sstream> #include <map> #include <stack> #include <set> #include <queue> #include <deque> #include <unordered_set> #include <unordered_map> #include <math.h> #include <cmath> #include <vector> #include <iomanip> #include <random> #include <chrono> #include <bitset> #include <cassert> using namespace std; #define ll long long #define fr first #define sc second #define pb push_back #define US freopen(".in", "r", stdin); freopen(".out", "w", stdout); ll gcd(ll a, ll b) { if (a == 0 || b == 0) { return max(a, b); } if (a <= b) { return gcd(a, b % a); } else { return gcd(a % b, b); } } ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; } const int N = 500005; const ll oo = 1000000000000000000, MOD = 1000000007; vector<int> patas, g[N]; bool ok[N]; void dfs(int u) { ok[u] = 1; patas.pb(u); for (int num : g[u]) { if (ok[num] == 0) { dfs(num); break; } } } std::vector<int> longest_trip(int N, int D) { int n = N, d = D; for (int i = 0; i < n; ++i) { ok[i] = 0; g[i].clear(); } patas.clear(); vector<int> vec; if (d == 3) { for (int i = 0; i < n; ++i) { vec.pb(i); } return vec; } int sk1 = 0, mx = 0; int mn = n * n + 3; vector<int> hnaravora; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (are_connected({ i }, { j }) == 1) { g[i].pb(j); g[j].pb(i); mx = max(mx, (int)g[i].size()); mx = max(mx, (int)g[j].size()); mn = min(mx, (int)g[i].size()); mn = min(mx, (int)g[j].size()); } else { if (hnaravora.size() == 0) { hnaravora.pb(i); } } } } vector<pair<int, int>> sortav; for (int i = 0; i < n; ++i) { sortav.pb({ g[i].size(),i }); } sort(sortav.begin(), sortav.end()); int l1 = min(20, (int)sortav.size()); for (int i = 0; i < l1; ++i) { hnaravora.pb(sortav[i].sc); } int r1 = (max(0, (int)sortav.size() - 20)); for (int i = 30; i < r1; ++i) { hnaravora.pb(sortav[i].sc); } for (int i = sortav.size() - 1; i >= r1; --i) { hnaravora.pb(sortav[i].sc); } for (int i = hnaravora.size()-1; i >= 0; --i) { for (int j = 0; j <= n; ++j) { ok[j] = 0; } patas.clear(); dfs(hnaravora[i]); if (patas.size() > vec.size()) { vec.clear(); vec = patas; } } return vec; }
#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...