Submission #251278

#	Time	Username	Problem	Language	Result	Execution time	Memory
251278		AaronNaidu	Dreaming (IOI13_dreaming)	C++14	47 / 100	160 ms	15300 KiB

dreaming

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

vector<pair<int, int>> graph[100001];
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]});
    }
    dfs(0, -1, 0);    
    //cout << "Done dfs1 landed on " << maxNode << "\n";
    int dfsFrom = maxNode;
    maxDist = 0;
    maxNode = dfsFrom;
    dfs(dfsFrom, -1, 0);
    //cout << "Done dfs2 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;
            }
        }
    }
    //cout << "Cand dists are " << currDist << " " << prevCurrDist << " out of " << maxDist << "\n";
    int ans1 = min(max(currDist, maxDist - currDist), max(prevCurrDist, maxDist - prevCurrDist));
    int start2 = 0;
    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            //cout << "Starting from " << start2 << "\n";
            break;
        }
        start2++;
    }
    maxDist = 0;
    maxNode = start2;
    dfs(start2, -1, 0);
    //cout << "Done dfs3 landed on " << maxNode << "\n";
    dfsFrom = maxNode;
    maxDist = 0;
    maxNode = dfsFrom;
    dfs(dfsFrom, -1, 0);
    //cout << "Done dfs4 landed on " << maxNode << "\n";
    currDist = maxDist;
    prevCurrDist = currDist;
    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;
            }
        }
    }
    //cout << "Cand dists are " << currDist << " " << prevCurrDist << " out of " << maxDist << "\n";
    int ans2 = min(max(currDist, maxDist - currDist), max(prevCurrDist, maxDist - prevCurrDist));
    //cout << "Ans 1 is " << ans1 << "\n";
    //cout << "Ans 2 is " << ans2 << "\n";
    return max(ans1 + ans2 + l, maxWithinDist);
}

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