Submission #139732

#TimeUsernameProblemLanguageResultExecution timeMemory
139732muradeynShortcut (IOI16_shortcut)C++14
0 / 100
2 ms376 KiB
#include "shortcut.h" #include <bits/stdc++.h> #define F first #define S second using namespace std; const int maxx = 6000; const long long inf = 10000000000000000LL; int n , nxt; long long x , w , old , res , mn; long long adj[maxx][maxx] , d[maxx]; priority_queue< pair<long long,int> >q; void bfs(int s) { for (int i = 0;i<nxt;i++)d[i] = inf; d[s] = 0; q.push( {0 , s} ); while (!q.empty()) { x = q.top().S; w = q.top().F; q.pop(); if (-w > d[x])continue; for (int i = 0;i<nxt;i++) { if (adj[x][i] == 0)continue; if (d[i] > d[x] + adj[x][i]) { d[i] = d[x] + adj[x][i]; q.push({-d[i] , i}); } } } } long long find_shortcut(int n, vector<int> l, vector<int> de, int c) { for (int i = 0;i < n - 1;i++) adj[i][i + 1] = adj[i + 1][i] = l[i]; nxt = n; for (int i = 0;i < n;i++) { if (de[i] == 0)continue; adj[i][nxt] = adj[nxt++][i] = de[i]; } for (int k = 0;k<nxt;k++) { bfs(k); for (int ii = 0;ii<nxt;ii++)mn = max(mn , d[ii]); } res = mn; for (int i = 0;i < n;i++) { for (int j = i + 1;j < n;j++) { old = adj[i][j]; adj[i][j] = adj[j][i] = c; mn = 0; for (int k = 0;k<nxt;k++) { bfs(k); for (int ii = 0;ii<nxt;ii++) mn = max(mn , d[ii]); } if (res == 0)res = mn; else if (mn < res)res = mn; adj[i][j] = adj[j][i] = old; } } return res; }

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:43:24: warning: operation on 'nxt' may be undefined [-Wsequence-point]
   adj[i][nxt] = adj[nxt++][i] = de[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...