Submission #776426

#	Time	Username	Problem	Language	Result	Execution time	Memory
776426		caganyanmaz	Dreaming (IOI13_dreaming)	C++17	100 / 100	59 ms	20964 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
//#define ONLINE_JUDGE
#ifdef ONLINE_JUDGE
#define debug(x) cout << (#x) << ": " << (x) << "\n"
#else
#define debug(x)
#endif
#define pb push_back

constexpr static int MXSIZE = 100000;
vector<array<int, 2>> g[MXSIZE];
int max_dist[MXSIZE];
int component[MXSIZE];
int radius[MXSIZE];
int n, m, l;
int worst;


void dfs1(int node, int parent, int comp)
{
        component[node] = comp;
        for (auto [c, cc] : g[node])
        {
                if (c != parent)
                {
                        dfs1(c, node, comp);
                        max_dist[node] = max(max_dist[node], max_dist[c] + cc);
                }
        }
}

void dfs2(int node, int parent, int cdist)
{
        vector<int> dd(3);
        for (auto [c, cc] : g[node])
        {
                if (c == parent)
                        continue;
                dd[0] = max_dist[c] + cc;
                sort(dd.begin(), dd.end());
        }
        worst = max(worst, dd[1] + dd[2]);
        radius[component[node]] = min(radius[component[node]], max(dd[2], cdist));
        for (auto [c, cc] : g[node])
        {
                if (c == parent)
                        continue;
                int j = 2;
                if (max_dist[c]+cc == dd[j])
                        j--;
                dfs2(c, node, max(cdist, dd[j]) + cc);
        }
}


int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
        n = N;
        m = M;
        l = L;
        for (int i = 0; i < m; i++)
        {
                g[A[i]].pb({B[i], T[i]});
                g[B[i]].pb({A[i], T[i]});
        }
        for (int i = 0; i < n; i++)
                component[i] = -1;
        int k = 0;
        for (int i = 0; i < n; i++)
        {
                if (component[i] == -1)
                {
                        radius[k] = 1e9;
                        dfs1(i, -1, k++);
                        dfs2(i, -1, 0);
                        if (radius[k-1] == 10)
                                debug(i);
                }
        }
        sort(radius, radius + k);
        debug(worst);
        debug(k);
        debug(radius[k-1]);
        debug(radius[k-2]);
        debug(radius[k-3]);
        if (k >= 2)
                worst = max(worst, radius[k-1] + radius[k-2] + l);
        if (k >= 3)
                worst = max(worst, radius[k-2] + radius[k-3] + 2 * l);
        return worst;

}

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