Submission #1265600

#TimeUsernameProblemLanguageResultExecution timeMemory
1265600gustavo_dShortcut (IOI16_shortcut)C++20
0 / 100
11 ms23876 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") typedef long long ll; const int MAXN = 1e6; ll pfAll[MAXN], sfAll[MAXN], pos[MAXN]; int pfSrc[MAXN], sfSrc[MAXN]; ll dist[MAXN]; vector<pair<int, ll>> adj[MAXN]; int N; void Dijkstra(int src) { for (int i=0; i<N; i++) dist[i] = 1e18; dist[src] = 0; priority_queue< pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>> > pq; pq.push({0, src}); while (!pq.empty()) { auto [d, v] = pq.top(); pq.pop(); if (d > dist[v]) continue; for (auto [viz, w] : adj[v]) { // cout << v << "->" << viz << endl; // cout << dist[viz] << ' ' << d << ' ' << w << endl; if (dist[viz] > d + w) { // cout << "ok" << endl; dist[viz] = d + w; pq.push({dist[viz], viz}); } } } } ll find_shortcut(int n, vector<int> l, vector<int> d, int c) { for (int i=0; i<n-1; i++) { adj[i].emplace_back(i+1, l[i]); adj[i+1].emplace_back(i, l[i]); } for (int i=0; i<n; i++) { adj[i].emplace_back(n+i, d[i]); adj[n+i].emplace_back(i, d[i]); } N = 2*n; ll res = 1e18; for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { adj[i].emplace_back(j, c); adj[j].emplace_back(i, c); Dijkstra(0); int p1 = 0; for (int k=0; k<N; k++) { if (dist[k] > dist[p1]) p1 = k; } Dijkstra(p1); ll tmp = 0; for (int k=0; k<N; k++) { tmp = max(tmp, dist[k]); } res = min(res, tmp); adj[i].pop_back(); adj[j].pop_back(); } } return res; // pfAll[0] = d[0]; pfSrc[0] = 0; // for (int i=0; i<n-1; i++) { // pfAll[i+1] = max((ll)d[i+1], pfAll[i] + l[i]); // pfSrc[i+1] = (d[i+1] > pfAll[i] + l[i] ? i+1 : pfSrc[i]); // } // sfAll[n-1] = d[n-1]; sfSrc[n-1] = n-1; // for (int i=n-2; i>=0; i--) { // sfAll[i] = max((ll)d[i], sfAll[i+1] + l[i]); // sfSrc[i] = (d[i] > sfAll[i+1] + l[i] ? i : sfSrc[i+1]); // } // int ans = 0; // for (int i=0; i<n; i++) { // ans = (pfAll[i] + sfAll[i] > pfAll[ans] + sfAll[ans] ? i : ans); // } // vector<ll> diam; bool left = true, right = true; // if (d[pfSrc[ans]] > 0) { // left = false; // diam.push_back(d[pfSrc[ans]]); // } // for (int i=pfSrc[ans]; i<sfSrc[ans]; i++) { // diam.push_back(l[i]); // } // if (d[sfSrc[ans]] > 0) { // diam.push_back(d[sfSrc[ans]]); // right = false; // } // N = n = (int)diam.size() + 1; // for (int i=0; i<n-1; i++) { // adj[i].emplace_back(i+1, diam[i]); // adj[i+1].emplace_back(i, diam[i]); // } // // pos[0] = 0; // // for (int i=1; i<n; i++) pos[i] = pos[i-1] + diam[i-1]; // ll res = 1e18; // for (int i=(!left); i<n; i++) { // for (int j=i; j<n-(!right); j++) { // adj[i].emplace_back(j, c); // adj[j].emplace_back(i, c); // Dijkstra(0); // int p1 = 0; // for (int i=0; i<n; i++) { // if (dist[i] > dist[p1]) i = p1; // } // Dijkstra(p1); // ll tmp = 0; // for (int i=0; i<n; i++) { // tmp = max(tmp, dist[i]); // } // if (tmp < res) { // cout << tmp << ' ' << i << ' ' << j << endl; // } // res = min(res, tmp); // adj[i].pop_back(); adj[j].pop_back(); // } // } // return res; // for (int i=0; i<n; i++) cout << pos[i] << ' '; // cout << endl; // ll lAns = c, rAns = pos[n-1], res = pos[n-1]; // while (lAns <= rAns) { // ll mid = (lAns + rAns) / 2; // cout << lAns << ' ' << rAns << ':' << mid << endl; // bool check = false; int k = 0; // for (int i=0; i<n; i++) { // if (pos[i] < mid) k = i; // } // cout << k << endl; // if (k == n-1) check = true; // for (int i=0+(!left), j=0; i<=k and !check; i++) { // bool stop = false; // while (!stop and pos[i] + c + pos[n-1] - pos[j] > mid) { // if (j == n-1-(!right)) stop = true; // j++; // } // if (stop) break; // if (pos[i] + c + max(pos[j] - pos[k], pos[n-1]-pos[j]) <= mid) { // cout << i << ' ' << j << endl; // check = true; // } // } // if (check) { // res = mid; // rAns = mid-1; // } else lAns = mid+1; // } // return res; }

Compilation message (stderr)

shortcut.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
shortcut_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...