Submission #1042386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042386		baldwinhuang1	Shortcut (IOI16_shortcut)	C++14	0 / 100	2095 ms	2140 KiB

shortcut

#include <bits/stdc++.h>

using namespace std;

vector< vector<int> > nodes;
vector< vector<int> > weights;

const long long INF = 1e18;


long long dist[1000][1000] ;// Voy a hacer subtask 1, el 1000 es para estar seguro

void floydWarshall(int n)
{
    int i, j, k;

    for (int i = 0; i < (n); i++) {
        for (int j = 0; j < (n + n); j++) {
            dist[i][j] = INF;
        }
    }

    for (int i = 0; i < (n); i++) {
        for (int j = 0; j < (n); j++) {
            if (i == j) {
                dist[i][j] = 0;
            }
            else if (nodes[i][j] == true) {
                dist[i][j] = min(dist[i][j], (long long)weights[i][j]);
            }
        }
    }

    for (k = 0; k < (n); k++) {
        for (i = 0; i < (n); i++) {
            for (j = 0; j < (n); j++) {
                if (dist[i][j] > (dist[i][k] + dist[k][j])
                    && (dist[k][j] != INF
                        && dist[i][k] != INF))
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

long long find_shortcut(int n, vector <int> l, vector <int> d, int c) {

    for (auto &i: d) {
        if (i != 0) {
            n++;
        }
    }
 
    nodes = vector< vector<int> >(n, vector<int>(n));
    weights = vector< vector<int> >(n, vector<int>(n));
 
    // cout << n << '\n';
 
    for (int i = 0; i < l.size(); i++) {
        // cout << i << '\n';
        nodes[i][i + 1] = true;
        nodes[i + 1][i] = true;
        weights[i][i + 1] = l[i];
        weights[i + 1][i] = l[i];
    }
 
    int j = l.size() + 1;
    for (int i = 0; i < d.size(); i++) {
        if (d[i] != 0) {
            // cout << i << ' ' << j << '\n';
            nodes[i][j] = true;
            nodes[j][i] = true;
            weights[i][j] = d[i];
            weights[j][i] = d[i];    
            j++;
        }
 
    }

    floydWarshall(n);

    // for (int i = 0; i < (n); i++) {
    //     for (int j = 0; j < (n); j++) {
    //         cout << dist[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }

    long long minimo = 1e18;
    for (int i = 0; i < (n - 1); i++) {
        for (int j = (i + 1); j < n; j++) {
            if (i != j && i <= l.size() && j <= l.size()) {
                // cout << "############" << '\n';
                int node1 = nodes[i][j];
                int node2 = nodes[j][i];
                int weight1 = weights[i][j];
                int weight2 = weights[j][i];
                nodes[i][j] = true;
                nodes[j][i] = true;
                if (weights[i][j] != 0) {
                    weights[i][j] = min(weights[i][j], c);
                }
                else {
                    weights[i][j] = c;
                }
                if (weights[j][i] != 0) {
                    weights[j][i] = min(weights[j][i], c);
                }
                else {
                    weights[j][i] = c;
                }
                floydWarshall(n);
                long long ans = 0;
                for (int i = 0; i < (n); i++) {
                    for (int j = 0; j < (n); j++) {
                        ans = max(ans, dist[i][j]);
                    }
                }
                // cout << ans << ' ' << i << ' ' << j << '\n';
                minimo = min(ans, minimo);
                nodes[i][j] = node1;
                nodes[j][i] = node2;
                weights[i][j] = weight1;
                weights[j][i] = weight2;
            }
        }
    }
    return minimo;
}

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < l.size(); i++) {
      |                     ~~^~~~~~~~~~
shortcut.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 0; i < d.size(); i++) {
      |                     ~~^~~~~~~~~~
shortcut.cpp:92:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             if (i != j && i <= l.size() && j <= l.size()) {
      |                           ~~^~~~~~~~~~~
shortcut.cpp:92:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             if (i != j && i <= l.size() && j <= l.size()) {
      |                                            ~~^~~~~~~~~~~

• 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