Submission #1057066

#TimeUsernameProblemLanguageResultExecution timeMemory
1057066fv3Shortcut (IOI16_shortcut)C++14
0 / 100
2052 ms440 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; vector<vector<pair<int, ll>>> adj; int N; vector<int> visited; vector<ll> dist; ll find_diameter() { ll longest = 0; for (int i = N / 2; i < N; i++) { visited = vector<int>(N); dist = vector<ll>(N, 1ll << 60); priority_queue<pair<ll, int>> q; q.push({0, i}); dist[i] = 0; int cnt = 0; while (1) { int s = q.top().second; q.pop(); if (visited[s]) continue; visited[s] = 1; cnt++; for (auto node : adj[s]) { if (visited[node.first] || dist[s] + node.second > dist[node.first]) continue; dist[node.first] = dist[s] + node.second; q.push({-dist[node.first], node.first}); } if (cnt == N) { longest = max(longest, dist[s]); break; } } } return longest; } ll find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { N = 2 * n; adj.resize(N); for (int i = 0; i < n - 1; i++) { adj[i].push_back({i+1, l[i]}); adj[i+1].push_back({i, l[i]}); } for (int i = 0; i < n; i++) { adj[i].push_back({i+n, d[i]}); adj[i+n].push_back({i, d[i]}); } ll res = 1ll << 60; for (int i = 0; i < n - 1; i++) { for (int j = i+1; j < n; j++) { adj[i].push_back({j, c}); adj[j].push_back({i, c}); res = min(res, find_diameter()); adj[i].pop_back(); adj[j].pop_back(); } } return res; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...