제출 #299452

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299452		c4ts0up	Shortcut (IOI16_shortcut)	C++17	0 / 100	17 ms	23936 KiB

shortcut

// c4ts0up
// Alvaro Bacca - COL3

#include "shortcut.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second
typedef long long ll;

const ll NMAX = 1e6+5, INF = 1e17;

vector <ll> dist, padre;
vector <ll> secundaria;
vector <pair <ll,ll> > Adj[NMAX];

// Anade en todas las distancias las lineas secundarias
void LineasSec(int n) {
    for (int i=0; i<n; i++) dist[i] += secundaria[i];
}

pair <ll,ll> Dijkstra(int n, ll source) {
    priority_queue <pair <ll,ll>, vector <pair <ll,ll> > , greater <pair <ll,ll> > > pq;
    pq.push({0LL, source});
    for (int i=0; i<n; i++) dist[i] = INF;

    while (!pq.empty()) {
        pair <ll,ll> curr = pq.top();
        pq.pop();

        if (dist[curr.ss] > curr.ff) {
            dist[curr.ss] = curr.ff;
            for (pair <ll,ll> p : Adj[curr.ss]) {
                pq.push({p.ff + dist[curr.ss], p.ss});
            }
        }
    }

    LineasSec(n);
    /*//
    cout << "Source: " << source << endl;
    for (int i=0; i<n; i++) {
        cout << "dist[" << i << "] = " << dist[i] << endl;
    }
    //*/

    pair <ll,ll> maxi = {0,0};
    for (int i=0; i<n; i++) {
        maxi = max(maxi, {(ll)dist[i] + secundaria[source],(ll)i});
    }
    return maxi;
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    // Crea la suma de prefijos
    dist.resize(n);
    padre.resize(n);

    int aux;
    //cout << "OK? ";
    //cin >> aux;

    for (int x : d) secundaria.pb((ll)(x));

    for (ll i=0; i<n-1; i++) {
        Adj[i].pb({(ll)l[i], i+1});
        Adj[i+1].pb({(ll)l[i], i});
    }

    ll diam = INF;

    //cout << "OK? ";
    //cin >> aux;

    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (i == j) continue;

            // si se construye entre i y j
            Adj[i].pb({(ll)(c), j});
            Adj[j].pb({(ll)(c), i});

            pair <ll,ll> pd1 = Dijkstra(n, i);
            pair <ll,ll> pd2 = Dijkstra(n, pd1.ss);
            LineasSec(n);

            //cout << "<" << i << ", " << j << "> : " << pd2.ff << endl;
            //cin >> aux;

            diam = min(diam, pd2.ff);

            Adj[i].pop_back();
            Adj[j].pop_back();
        }
    }

    //cout << "Finished" << endl;

    return diam;
}

컴파일 시 표준 에러 (stderr) 메시지

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:61:9: warning: unused variable 'aux' [-Wunused-variable]
   61 |     int aux;
      |         ^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3