Submission #197932

#	Time	Username	Problem	Language	Result	Execution time	Memory
197932		johutha	Dreaming (IOI13_dreaming)	C++14	18 / 100	90 ms	14584 KiB

dreaming

#include "dreaming.h"
#include <vector>
#include <iostream>
#include <algorithm>

#define int int64_t

using namespace std;

struct graph
{
    int n;
    vector<vector<pair<int,int>>> adjlist;
    vector<int> comp;
    vector<int> dist;
    int nrcomp = 0;

    pair<int,int> compdfs(int curr, int par, int c)
    {
        comp[curr] = c;

        int mmax = 0;
        int mver = curr;

        for (auto p : adjlist[curr])
        {
            int next = p.first;
            int w = p.second;
            if (next == par) continue;
            auto pn = compdfs(next, curr, c);
            pn.second += w;
            if (pn.second > mmax)
            {
                mmax = pn.second;
                mver = pn.first;
            }
        }

        return {mver, mmax};
    }

    void distdfs(int curr, int par, int d)
    {
        dist[curr] = max(dist[curr], d);

        for (auto p : adjlist[curr])
        {
            int next = p.first;
            int w = p.second;
            if (next == par) continue;
            distdfs(next, curr, d + w);
        }
    }

    int calc(int l)
    {
        dist.resize(n, -1);
        comp.resize(n, -1);

        for (int i = 0; i  < n; i++)
        {
            if (comp[i] == -1)
            {
                comp[i] = nrcomp;
                auto rp = compdfs(i, -1, nrcomp);
                distdfs(rp.first, -1, 0);
                nrcomp++;
            }
        }

        vector<int> md(nrcomp, -1);
        vector<int> mv(nrcomp, -1);

        for (int i = 0; i < n; i++)
        {
            if (dist[i] > md[comp[i]])
            {
                md[comp[i]] = dist[i];
                mv[comp[i]] = i;
            }
        }

        for (auto j : mv)
        {
            distdfs(j, -1, 0);
        }

        md.assign(nrcomp, (int)1e12);
        for (int i = 0; i < n; i++)
        {
            if (dist[i] < md[comp[i]])
            {
                md[comp[i]] = dist[i];
            }
        }

        sort(md.begin(), md.end());
        if (nrcomp <= 2)
        {
            int ssum = 0;
            for (auto i : md) ssum += i;
            if (nrcomp == 2) ssum += l;
            return ssum;
        }

        return max(md[nrcomp - 1] + md[nrcomp - 2] + l, md[nrcomp - 2] + md[nrcomp - 3] + 2*l);
    }

    void print()
    {
        for (int i = 0; i < n; i++)
        {
            if (i < 10) cout << " ";
            cout << i << " ";
        }
        cout << "\n";
        for (auto i : comp)
        {
            if (i < 10) cout << " ";
            cout << i << " ";
        }
        cout << "\n";

        for (auto i : dist)
        {
            if (i < 10) cout << " ";
            cout << i << " ";
        }
        cout << "\n";
    }
};

signed travelTime(signed N, signed M, signed L, signed A[], signed B[], signed T[])
{
    graph g;
    g.n = N;

    g.adjlist.resize(N);

    for (int i = 0; i < M; i++)
    {
        g.adjlist[A[i]].emplace_back(B[i], T[i]);
        g.adjlist[B[i]].emplace_back(A[i], T[i]);
    }

    return g.calc(L);
}

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