Submission #228349

#	Time	Username	Problem	Language	Result	Execution time	Memory
228349		AaronNaidu	Shortcut (IOI16_shortcut)	C++14	0 / 100	94 ms	198392 KiB

shortcut

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<pair<int, int> > graph[100000];
ll dist1s[100000];
bool visited[100000];
ll distMatrix[5000][5000];

void DFS(int node) {
    visited[node] = true;
    for (auto i : graph[node])
    {
        if (!visited[i.first])
        {
            dist1s[i.first] = i.second + dist1s[node];
            DFS(i.first);
        }
    }
}

ll find_shortcut(int n, vector<int> l, vector<int> d, int c) {
    cout << "Starting\n";
    for (int i = 0; i < l.size(); i++)
    {
        graph[i].push_back({i+1, l[i]});
        graph[i+1].push_back({i, l[i]});
    }
    for (int i = 0; i < d.size(); i++)
    {
        if (d[i] > 0)
        {
            graph[i].push_back({i+n, d[i]});
            graph[i+n].push_back({i, d[i]});
        }
    }
    cout << "Starting first DFS\n";
    DFS(0);
    cout << "Done with first DFS\n";
    ll maxDist = 0;
    int maxVert = -1;
    for (int i = 0; i < 2 * n; i++)
    {
        if (maxDist < dist1s[i])
        {
            maxDist = dist1s[i];
            maxVert = i;
        }
        dist1s[i] = 0;
        visited[i] = false;
    }
    DFS(maxVert);
    ll maxDist2 = 0;
    int maxVert2 = -1;
    for (int i = 0; i < 2 * n; i++)
    {
        if (maxDist2 < dist1s[i])
        {
            maxDist2 = dist1s[i];
            maxVert2 = i;
        }
        dist1s[i] = 0;
    }
    if (maxVert >= n)
    {
        maxVert -= n;
    }
    if (maxVert2 >= n)
    {
        maxVert2 -= n;
    }
    
    graph[maxVert].push_back({maxVert2, c});
    graph[maxVert2].push_back({maxVert, c});
    cout << "Edge between " << maxVert << " and " << maxVert2 << "\n";
    priority_queue<pair<ll, ll> > q;
    for (int i = 0; i < 5000; i++)
    {
        for (int j = 0; j < 5000; j++)
        {
            distMatrix[i][j] = 1000000000000000000;
        }
        
    }
    
    for (int i = 0; i < 2 * n; i++)
    {
        q.push({0, i});
        for (int j = 0; j < 2 * n; j++)
        {
            visited[j] = false;
        }
        distMatrix[i][i] = 0;
        while (!q.empty())
        {
            int dist = -q.top().first;
            int node = q.top().second;
            q.pop();
            if (visited[node])
            {
                continue;
            }
            visited[node] = true;
            for (auto j : graph[node])    
            {
                if (!visited[j.first])
                {
                    distMatrix[i][j.first] = min(distMatrix[i][j.first], distMatrix[i][node] + j.second);
                    //cout << "Updating distMatrix " << i << j.first << " to " <<  min(distMatrix[i][j.first], distMatrix[i][node] + j.second) << "\n";
                    q.push({-distMatrix[i][j.first], j.first});
                }
            }
        }
    }
    ll toRet = 0;
    for (int i = 0; i < 2 * n; i++)
    {
        for (int j = 0; j < 2 * n; j++)
        {
            if (distMatrix[i][j] < 1000000000000000000)
            {
                toRet = max(toRet, distMatrix[i][j]);
            }
        }
    }
    return toRet;
}

Compilation message (stderr)

shortcut.cpp: In function 'll find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < l.size(); i++)
                     ~~^~~~~~~~~~
shortcut.cpp:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < d.size(); i++)
                     ~~^~~~~~~~~~
shortcut.cpp:96:17: warning: unused variable 'dist' [-Wunused-variable]
             int dist = -q.top().first;
                 ^~~~

• 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