Submission #744296

#TimeUsernameProblemLanguageResultExecution timeMemory
744296nhphucqtRelay Marathon (NOI20_relaymarathon)C++17
0 / 100
6 ms8916 KiB
#include <bits/stdc++.h> using namespace std; const long long MAX = 0x3f3f3f3f3f3f3f3f; template<typename T> bool minimize(T&x,T y) { return x > y ? x = y, true : false; } int buckSiz; pair<long long, int> bucket[8]; struct FourMin { pair<long long, int> v[4]; FourMin() { for (int i = 0; i < 4; ++i) { v[i] = make_pair(MAX, -1); } } FourMin operator + (long long x) const { FourMin tmp; for (int i = 0; i < 4; ++i) { if (v[i].second != -1) { tmp.v[i].first = v[i].first + x; tmp.v[i].second = v[i].second; } } return tmp; } bool update(const FourMin& val) { buckSiz = 0; for (int i = 0; i < 4; ++i) { bucket[buckSiz++] = v[i]; bucket[buckSiz++] = val.v[i]; } sort(bucket, bucket+buckSiz); bool flag = false; int j = 0; for (int i = 0; i < buckSiz; ++i) { bool found = false; for (int k = 0; k < j; ++k) { if (v[k].second == bucket[i].second && bucket[i].second != -1) { found = true; break; } } if (!found) { flag |= v[j] > bucket[i]; v[j++] = bucket[i]; if (j == 4) { break; } } } return flag; } void update(const pair<long long, int>& x) { buckSiz = 0; for (int i = 0; i < 4; ++i) { bucket[buckSiz++] = v[i]; } bucket[buckSiz++] = x; sort(bucket,bucket+buckSiz); int j = 0; for (int i = 0; i < buckSiz; ++i) { bool found = false; for (int k = 0; k < j; ++k) { if (v[k].second == bucket[i].second && bucket[i].second != -1) { found = true; break; } } if (!found) { v[j++] = bucket[i]; if (j == 4) { break; } } } } bool operator < (const FourMin& val) const { for (int i = 0; i < 4; ++i) { if (v[i].first != val.v[i].first) { return v[i].first > val.v[i].first; } } return true; } bool operator != (const FourMin& val) const { for (int i = 0; i < 4; ++i) { if (v[i] != val.v[i]) { return true; } } return false; } friend ostream& operator << (ostream& os, const FourMin& val) { for (int i = 0; i < 4; ++i) { os << i << " -> " << val.v[i].first << ' ' << val.v[i].second << '\n'; os << "------\n"; } return os; } }; const int N = 1e5+7; int numNode, numEdge, numSpec; vector<pair<int,int>> adj[N]; vector<int> specs; FourMin dist[N]; long long res; int src[2], snk[2]; int candSiz; pair<long long, pair<int,int>> candidates[N*4]; void dijkstra() { priority_queue<pair<FourMin, int>> heap; for (int x : specs) { dist[x].v[0] = make_pair(0, x); heap.emplace(dist[x], x); } while (!heap.empty()) { int u = heap.top().second; FourMin w = heap.top().first; // cerr << " >> " << u << '\n'; heap.pop(); if (dist[u] != w) { continue; } for (pair<int,int> e : adj[u]) { int v = e.first; int w = e.second; // cerr << u << ": \n" << (dist[u]); // cerr << v << ": \n" << dist[v]; if (dist[v].update(dist[u] + w)) { // cerr << v << ": \n" << dist[v]; heap.emplace(dist[v], v); } } } } bool deepdiff(const pair<int,int>& a, const pair<int,int>& b) { return a.first != b.first && a.first != b.second && a.second != b.first && a.second != b.second; } void processCaseOne() { pair<int,int> clos = candidates[0].second; // cerr << " >> "; // cerr << clos.first << ' ' << clos.second << '\n'; for (int i = 1; i < candSiz; ++i) { if (deepdiff(clos, candidates[i].second)) { res = candidates[0].first + candidates[i].first; src[0] = clos.first; snk[0] = clos.second; src[1] = candidates[i].second.first; snk[1] = candidates[i].second.second; return; } } } void updateResult(long long r, int _src1, int _snk1, int _src2, int _snk2) { if (minimize(res, r)) { src[0] = _src1; snk[0] = _snk1; src[1] = _src2; snk[1] = _snk2; } } void processCaseTwo() { int beg[2]; beg[0] = candidates[0].second.first; beg[1] = candidates[0].second.second; FourMin fm[2]; for (int i = 0; i < candSiz; ++i) { for (int j = 0; j < 2; ++j) { if (candidates[i].second.first == beg[j] && candidates[i].second.second != beg[!j]) { fm[j].update(make_pair(candidates[i].first, candidates[i].second.second)); } else if (candidates[i].second.second == beg[j] && candidates[i].second.first != beg[!j]) { fm[j].update(make_pair(candidates[i].first, candidates[i].second.first)); } } } for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { if (fm[0].v[i].second != fm[1].v[j].second) { updateResult(fm[0].v[i].first+fm[1].v[j].first, beg[0], fm[0].v[i].second, beg[1], fm[1].v[j].second); } } } } int main() { cin.tie(nullptr)->sync_with_stdio(false); freopen("marathon.inp", "r", stdin); freopen("marathon.out", "w", stdout); cin >> numNode >> numEdge >> numSpec; for (int i = 0; i < numEdge; ++i) { int x, y, w; cin >> x >> y >> w; adj[x].emplace_back(y, w); adj[y].emplace_back(x, w); } for (int i = 0; i < numSpec; ++i) { int x; cin >> x; specs.push_back(x); } dijkstra(); // for (int i = 1; i <= numNode; ++i) { // for (int j = 0; j < 4; ++j) { // cerr << i << " : " << j << " -> " << dist[i].v[j].first << ' ' << dist[i].v[j].second << '\n'; // } // } for (int i = 1; i <= numNode; ++i) { for (int j = 0; j < 4; ++j) for (int k = j+1; k < 4; ++k) { if (dist[i].v[j].second != -1 && dist[i].v[k].second != -1) { candidates[candSiz++] = make_pair(dist[i].v[j].first+dist[i].v[k].first, make_pair(dist[i].v[j].second, dist[i].v[k].second)); } } } sort(candidates, candidates+candSiz); processCaseOne(); processCaseTwo(); cout << res; // for (int i = 0; i < 2; ++i) { // cerr << " >>> " << src[i] << ' ' << snk[i] << '\n'; // } return 0; }

Compilation message (stderr)

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:206:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |     freopen("marathon.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
RelayMarathon.cpp:207:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |     freopen("marathon.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...