제출 #434946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434946		alextodoran	꿈 (IOI13_dreaming)	C++17	18 / 100	77 ms	14148 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> centers;
    vector <int> weights;
    {
        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;
                int center = -1;
                for(int v : nodes)
                {
                    int maxDist = max(maxDistDown[v], maxDistUp[v]);
                    if(maxDist < bestMaxDist)
                    {
                        bestMaxDist = maxDist;
                        center = v;
                    }
                }

                centers.push_back(center);
                weights.push_back(bestMaxDist);
            }
    }

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

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