Submission #1069761

#TimeUsernameProblemLanguageResultExecution timeMemory
1069761mc061Shortcut (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> vv = q.top(); int v = vv.second; q.pop(); for (int i = 0; i < graph[v].size(); ++i) { pair<int, int> uu = graph[v][i]; int u = uu.first; int w = uu.second; if (d[u] > d[v] + w) { d[u] = d[v] + w; q.push({d[u], u}); } } } pair<int64_t, int> ret = {-1e18, 69420123}; for (int i = 0; i < n; ++i) { 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]}); } int sz = n; for (int i = 0; i < n; ++i) { if (d[i] > 0) { graph[i].push_back({sz, d[i]}), graph[sz].push_back({i, d[i]}); sz++; } } int64_t res = 1e18; for (int i = 0; i < n; ++i) { for (int j = 3; j < n; ++j) { graph[i].push_back({j, c}); graph[j].push_back({i, c}); int64_t diam = 0; for (int k = 0; k < sz; ++k) { auto x = get_dists(graph, sz, k); diam = max(diam, x.first); } res = min(res, diam); 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:19: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]
   19 |         for (int i = 0; i < graph[v].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...