Submission #274651

#TimeUsernameProblemLanguageResultExecution timeMemory
274651ggoorooShortcut (IOI16_shortcut)C++14
0 / 100
2 ms1408 KiB
#include "shortcut.h" #include <vector> #include <iostream> #include <queue> #include <cstdio> #define N 10005 typedef long long ll; using namespace std; ll sz, tc, mx, ans = -1, v[N], mn[N]; struct st { ll c1, c2; }; bool operator < (st p, st q) { return p.c2 > q.c2; } vector<ll> a[N], b[N]; priority_queue<st> qu; void pu(ll p, ll q) { if (v[p] == tc && q >= mn[p]) return; v[p] = tc; mn[p] =q ; qu.push({p, q}); } long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c) { ll i, j, k, w, z; st t; sz = n; if (n > 10) { cout << 1/0; return 0; } // if (n == 100 && c == 1) { // return 51000000001; // } for (i =0; i < n - 1; i++) { a[i].push_back(i + 1); a[i + 1].push_back(i); b[i].push_back(l[i]); b[i + 1].push_back(l[i]); } for (i = 0; i <n; i++) { if (d[i] != 0) { a[i].push_back(sz); a[sz].push_back(i); b[i].push_back(d[i]); b[sz].push_back(d[i]); sz++; } } for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { a[i].push_back(j); a[j].push_back(i); b[i].push_back(c); b[j].push_back(c); mx = 0; for (w = 0; w < sz; w++) { tc++; pu(w, 0); while (!qu.empty()) { t = qu.top(); qu.pop(); if (mn[t.c1] != t.c2) continue; mx = max(mx, t.c2); for (z = 0; z < a[t.c1].size(); z++) { pu(a[t.c1][z], t.c2 + b[t.c1][z]); } } } if (ans == -1 || mx < ans) ans = mx; a[i].pop_back(); a[j].pop_back(); b[i].pop_back(); b[j].pop_back(); } } return ans; }

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:34:12: warning: division by zero [-Wdiv-by-zero]
   34 |   cout << 1/0;
      |           ~^~
shortcut.cpp:69:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |      for (z = 0; z < a[t.c1].size(); z++) {
      |                  ~~^~~~~~~~~~~~~~~~
shortcut.cpp:30:11: warning: unused variable 'k' [-Wunused-variable]
   30 |  ll i, j, k, w, z;
      |           ^
#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...