Submission #435224

#	Time	Username	Problem	Language	Result	Execution time	Memory
435224		alextodoran	Dreaming (IOI13_dreaming)	C++17	100 / 100	130 ms	21528 KiB

dreaming

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

typedef long long ll;

struct Edge
{
    int to;
    int len;
};

int travelTime (int n, int m, int lenNew, int edgeU[], int edgeV[], int edgeL[])
{
    vector <Edge> edges[n];
    for(int i = 0; i < m; i++)
    {
        edges[edgeU[i]].push_back(Edge{edgeV[i], edgeL[i]});
        edges[edgeV[i]].push_back(Edge{edgeU[i], edgeL[i]});
    }

    vector <int> weights;
    int maxDiam = 0;
    {
        int plen[n];

        int maxDistUp[n];
        int maxDistDown[n];
        int maxDistDown2[n];

        bool visited[n];
        vector <int> nodes;
        function <void (int, int)> DFSDown = [&] (int u, int parent)
        {
            nodes.push_back(u);
            visited[u] = true;

            maxDistDown[u] = 0;
            maxDistDown2[u] = 0;
            for(Edge e : edges[u])
                if(e.to != parent)
                {
                    plen[e.to] = e.len;
                    DFSDown(e.to, u);
                    if(maxDistDown[e.to] + e.len >= maxDistDown[u])
                    {
                        maxDistDown2[u] = maxDistDown[u];
                        maxDistDown[u] = maxDistDown[e.to] + e.len;
                    }
                    else if(maxDistDown[e.to] + e.len > maxDistDown2[u])
                        maxDistDown2[u] = maxDistDown[e.to] + e.len;
                }
        };
        function <void (int, int)> DFSUp = [&] (int u, int parent)
        {
            if(parent != -1)
            {
                maxDistUp[u] = maxDistUp[parent] + plen[u];
                if(maxDistDown[u] + plen[u] == maxDistDown[parent])
                    maxDistUp[u] = max(maxDistUp[u], maxDistDown2[parent] + plen[u]);
                else
                    maxDistUp[u] = max(maxDistUp[u], maxDistDown[parent] + plen[u]);
            }
            else
                maxDistUp[u] = 0;

            for(Edge e : edges[u])
                if(e.to != parent)
                    DFSUp(e.to, u);
        };
        for(int u = 0; u < n; u++)
            visited[u] = false;
        for(int u = 0; u < n; u++)
            if(visited[u] == false)
            {
                nodes.clear();
                DFSDown(u, -1);
                DFSUp(u, -1);

                int bestMaxDist = INT_MAX;
                for(int v : nodes)
                {
                    int maxDist = max(maxDistDown[v], maxDistUp[v]);
                    maxDiam = max(maxDiam, maxDist);
                    bestMaxDist = min(bestMaxDist, maxDist);
                }

                weights.push_back(bestMaxDist);
            }
    }

    sort(weights.begin(), weights.end());
    if((int)weights.size() == 1)
        return maxDiam;
    else if((int)weights.size() == 2)
        return max(weights.end()[-1] + weights.end()[-2] + lenNew,
                   maxDiam);
    else
        return max({weights.end()[-1] + weights.end()[-2] + lenNew,
                    weights.end()[-2] + weights.end()[-3] + lenNew * 2,
                    maxDiam});
}

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