Submission #1069722

#TimeUsernameProblemLanguageResultExecution timeMemory
1069722mc061Shortcut (IOI16_shortcut)C++14
0 / 100
1 ms348 KiB
#pragma once #include <bits/stdc++.h> using namespace std; template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>; const int64_t INF = 1e18; pair<int64_t, int> get_dists(const vector<vector<pair<int, int>>>& graph, int n, int s=0) { vector<int64_t> d(n, INF); d[s] = 0; minheap<pair<int64_t, int>> q; q.push({0, s}); while (!q.empty()) { pair<int64_t, int> v = q.top(); q.pop(); for (int i = 0; i < graph[v.second].size(); ++i) { pair<int, int> u = graph[v.second][i]; if (d[u.first] > d[v.second] + u.second) { d[u.first] = d[v.second] + u.second; q.push({d[u.first], u.first}); } } } pair<int64_t, int> ret = {-1e18, 69420123}; for (int i = 0; i < n; ++i) { if (d[i] != INF) ret = max(ret, {d[i], i}); } return ret; } long long find_shortcut(int n, vector<int> l, vector<int> d, int c) { vector<vector<pair<int, int>>> graph(2*n); for (int i = 0; i+1 < n; ++i) { graph[i].push_back({i+1, l[i]}); graph[i+1].push_back({i, l[i]}); } for (int i = 0; i < n; ++i) { if (d[i] > 0) graph[i].push_back({i+n, d[i]}), graph[i+n].push_back({i, d[i]}); } int64_t res = 1e18; for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { graph[i].push_back({j, c}); graph[j].push_back({i, c}); auto x = get_dists(graph, 2*n); int64_t now = get_dists(graph, 2*n, x.second).first; res = min(res, now); graph[i].pop_back(); graph[j].pop_back(); } } return res; }

Compilation message (stderr)

shortcut.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut.cpp: In function 'std::pair<long int, int> get_dists(const std::vector<std::vector<std::pair<int, int> > >&, int, int)':
shortcut.cpp:18:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for (int i = 0; i < graph[v.second].size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...