oj.uz

답안 #299452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
299452 2020-09-14T23:14:20 Z c4ts0up Shortcut (IOI16_shortcut) C++17
0 / 100
 17 ms 23936 KB 
// 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;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB n = 4, 80 is a correct answer
2 Correct 17 ms 23936 KB n = 9, 110 is a correct answer
3 Correct 17 ms 23808 KB n = 4, 21 is a correct answer
4 Correct 17 ms 23936 KB n = 3, 4 is a correct answer
5 Incorrect 16 ms 23808 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB n = 4, 80 is a correct answer
2 Correct 17 ms 23936 KB n = 9, 110 is a correct answer
3 Correct 17 ms 23808 KB n = 4, 21 is a correct answer
4 Correct 17 ms 23936 KB n = 3, 4 is a correct answer
5 Incorrect 16 ms 23808 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB n = 4, 80 is a correct answer
2 Correct 17 ms 23936 KB n = 9, 110 is a correct answer
3 Correct 17 ms 23808 KB n = 4, 21 is a correct answer
4 Correct 17 ms 23936 KB n = 3, 4 is a correct answer
5 Incorrect 16 ms 23808 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB n = 4, 80 is a correct answer
2 Correct 17 ms 23936 KB n = 9, 110 is a correct answer
3 Correct 17 ms 23808 KB n = 4, 21 is a correct answer
4 Correct 17 ms 23936 KB n = 3, 4 is a correct answer
5 Incorrect 16 ms 23808 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB n = 4, 80 is a correct answer
2 Correct 17 ms 23936 KB n = 9, 110 is a correct answer
3 Correct 17 ms 23808 KB n = 4, 21 is a correct answer
4 Correct 17 ms 23936 KB n = 3, 4 is a correct answer
5 Incorrect 16 ms 23808 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB n = 4, 80 is a correct answer
2 Correct 17 ms 23936 KB n = 9, 110 is a correct answer
3 Correct 17 ms 23808 KB n = 4, 21 is a correct answer
4 Correct 17 ms 23936 KB n = 3, 4 is a correct answer
5 Incorrect 16 ms 23808 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB n = 4, 80 is a correct answer
2 Correct 17 ms 23936 KB n = 9, 110 is a correct answer
3 Correct 17 ms 23808 KB n = 4, 21 is a correct answer
4 Correct 17 ms 23936 KB n = 3, 4 is a correct answer
5 Incorrect 16 ms 23808 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB n = 4, 80 is a correct answer
2 Correct 17 ms 23936 KB n = 9, 110 is a correct answer
3 Correct 17 ms 23808 KB n = 4, 21 is a correct answer
4 Correct 17 ms 23936 KB n = 3, 4 is a correct answer
5 Incorrect 16 ms 23808 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -