Submission #656969

#TimeUsernameProblemLanguageResultExecution timeMemory
656969pls33Cheap flights (LMIO18_pigus_skrydziai)C++17
100 / 100
354 ms42584 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #pragma region dalykai using p32 = pair<int, int>; using p32u = pair<uint32_t, uint32_t>; using p64 = pair<int64_t, int64_t>; using p64u = pair<uint64_t, uint64_t>; using vi16 = vector<int16_t>; using vi16u = vector<uint16_t>; using vi32 = vector<int>; using vi32u = vector<uint32_t>; using vi64 = vector<int64_t>; using vi64u = vector<uint64_t>; using vp32 = vector<p32>; using vp32u = vector<p32u>; using vp64 = vector<p64>; using vp64u = vector<p64u>; using vvi32 = vector<vi32>; using vvi32u = vector<vi32u>; using vvi64 = vector<vi64>; using vvi64u = vector<vi64u>; using vvp32 = vector<vp32>; using vvp32u = vector<vp32u>; using vvp64 = vector<vp64>; using vvp64u = vector<vp64u>; using pf32 = pair<float, float>; using pf64 = pair<double, double>; using pf80 = pair<long double, long double>; using vf32 = vector<float>; using vf64 = vector<double>; using vf80 = vector<long double>; using vpf32 = vector<pf32>; using vpf64 = vector<pf64>; using vpf80 = vector<pf80>; using vvf32 = vector<vf32>; using vvf64 = vector<vf64>; using vvf80 = vector<vf80>; using vvpf32 = vector<vpf32>; using vvpf64 = vector<vpf64>; using vvpf80 = vector<vpf80>; template <typename key, typename val> using ord_map = tree<key, val, less<key>, rb_tree_tag, tree_order_statistics_node_update>; template <typename key> using ord_set = tree<key, null_type, less<key>, rb_tree_tag, tree_order_statistics_node_update>; const int BUF_SZ = 1 << 15; inline namespace fast_in { char buf[BUF_SZ]; int pos; int len; char next_char(FILE *f) { if (pos == len) { pos = 0; len = (int)fread(buf, 1, BUF_SZ, f); if (!len) { return EOF; } } return buf[pos++]; } int read_int(FILE *f) { int x; char ch; int sgn = 1; while (!isdigit(ch = next_char(f))) { if (ch == '-') { sgn *= -1; } } x = ch - '0'; while (isdigit(ch = next_char(f))) { x = x * 10 + (ch - '0'); } return x * sgn; } } /** * @brief gale programos flush_out kviest!! */ inline namespace fast_out { char buf[BUF_SZ]; int pos; void flush_out(FILE *f) { fwrite(buf, 1, pos, f); pos = 0; } void write_char(char c, FILE *f) { if (pos == BUF_SZ) { flush_out(f); } buf[pos++] = c; } void write_int(int x, FILE *f) { static char num_buf[100]; if (x < 0) { write_char('-', f); x *= -1; } int len = 0; for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); } write_char((char)('0' + x), f); while (len) { write_char(num_buf[--len], f); } write_char('\n', f); } } #pragma endregion int main() { #ifndef _AAAAAAAAA ios_base::sync_with_stdio(false); cin.tie(0); #else freopen("flight.in", "r", stdin); #ifndef __linux__ atexit([]() { freopen("con", "r", stdin); system("pause"); }); #endif #endif int v, e; cin >> v >> e; vi64 sum(v); vvp32 adj(v), weight(v); for (int i = 0; i < e; i++) { int a, b, w; cin >> a >> b >> w; a--; b--; sum[a] += w; sum[b] += w; adj[a].emplace_back(b, w); adj[b].emplace_back(a, w); weight[a].emplace_back(w, b); weight[b].emplace_back(w, a); } for (int i = 0; i < v; i++) { sort(adj[i].begin(), adj[i].end()); sort(weight[i].rbegin(), weight[i].rend()); } int64_t result = *max_element(sum.begin(), sum.end()); for (int i = 0; i < v; i++) { if (adj[i].size() < 2) { continue; } int a = weight[i][0].second, b = weight[i][1].second; p32 __b = {b, 0}; auto it = lower_bound(adj[a].begin(), adj[a].end(), __b); if (it == adj[a].end() || it->first != b) { continue; } int64_t cur = (int64_t)it->second + weight[i][0].first + weight[i][1].first; result = max(result, cur); } cout << result << '\n'; return 0; }

Compilation message (stderr)

pigus_skrydziai.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
pigus_skrydziai.cpp:151: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  151 | #pragma endregion
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...