Submission #251286

#	Time	Username	Problem	Language	Result	Execution time	Memory
251286		AaronNaidu	Dreaming (IOI13_dreaming)	C++14	100 / 100	141 ms	15352 KiB

dreaming

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

vector<pair<int, int>> graph[100001];
vector<int> componentSums;
int dists[100001];
bool visited[100001];
int maxWithinDist = 0;
int maxDist = 0;
int maxNode = 0;

void dfs(int node, int parent, int dist) {
    dists[node] = dist;
    if (dist > maxDist)
    {
        maxWithinDist = max(maxWithinDist, dist);
        maxDist = dist;
        maxNode = node;
    }
    for (auto i : graph[node])
    {
        if (i.first != parent)
        {
            dfs(i.first, node, dist + i.second);
        }
    }
    visited[node] = true;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for (int i = 0; i < m; i++)
    {
        graph[a[i]].push_back({b[i],t[i]});
        graph[b[i]].push_back({a[i], t[i]});
    }
    int start2 = 0;
    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            maxDist = 0;
            maxNode = start2;
            dfs(start2, -1, 0);
            //cout << "Done dfs3 landed on " << maxNode << "\n";
            int dfsFrom = maxNode;
            maxDist = 0;
            maxNode = dfsFrom;
            dfs(dfsFrom, -1, 0);
            //cout << "Done dfs4 landed on " << maxNode << "\n";
            int currDist = maxDist;
            int prevCurrDist = currDist;
            int currNode = maxNode;
            while (float(currDist) > maxDist/float(2))
            {
                for (auto i : graph[currNode])
                {
                    if (dists[i.first] < dists[currNode])
                    {
                        currNode = i.first;
                        prevCurrDist = currDist;
                        currDist = dists[currNode];
                        break;
                    }
                }
            }
            int ans2 = min(max(currDist, maxDist - currDist), max(prevCurrDist, maxDist - prevCurrDist));
            componentSums.push_back(ans2);
        }
        start2++;
    }
    sort(componentSums.begin(), componentSums.end());
    if (componentSums.size() == 1)
    {
        return maxWithinDist;
    }
    if (componentSums.size() == 2)
    {
        return max(maxWithinDist, l + componentSums[0] + componentSums[1]);
    }
    for (auto i : componentSums)
    {
        //cout << "--- " << i << "\n";
    }
    //cout << "*** " << maxWithinDist << "\n";
    //cout << "Ans 1 is " << ans1 << "\n";
    //cout << "Ans 2 is " << ans2 << "\n";
    return max(maxWithinDist, max(componentSums[componentSums.size()-1] + componentSums[componentSums.size() - 2] + l, componentSums[componentSums.size() - 2] + componentSums[componentSums.size() - 3] + 2*l));
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:81:15: warning: unused variable 'i' [-Wunused-variable]
     for (auto i : componentSums)
               ^

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23