Submission #198097

#	Time	Username	Problem	Language	Result	Execution time	Memory
198097		johutha	Dreaming (IOI13_dreaming)	C++14	18 / 100	1018 ms	13816 KiB

dreaming

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

#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;

    void compdfs(int curr, int par, int c)
    {
        comp[curr] = c;

        for (auto p : adjlist[curr])
        {
            int next = p.first;
            if (next == par) continue;
            compdfs(next, curr, c);
        }
    }

    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);
        }
    }

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

    int calcdiameter()
    {
        dist.assign(n, -1);
        distdfs(0, -1, 0);
        int mmax = -1;
        int mver = -1;

        for (int i = 0; i < n; i++)
        {
			if (dist[i] == -1) return 1e15;
            if (mmax < dist[i])
            {
                mmax = dist[i];
                mver = i;
            }
        }
        dist.assign(n, -1);

        distdfs(mver, -1, 0);
        return *max_element(dist.begin(), dist.end());
    }

	int onecalc(int l)
	{
		int mmin = 1e15;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (comp[i] == comp[j]) continue;
				adjlist[i].emplace_back(j, l);
				adjlist[j].emplace_back(i, l);
				mmin = min(mmin, calcdiameter());
				adjlist[i].pop_back();
				adjlist[j].pop_back();
			}
		}
		return mmin;
	}

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

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

        if (nrcomp == 1)
        {
			return calcdiameter();
        }
		if (nrcomp == 2) return onecalc(l);

        for (int i = 0; i < n; i++)
        {
            if (dist[i] < 0)
            {
                distdfs(i, -1, 0);
            }
        }

        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 i : mv) distdfs(i, -1, 0);

        md.assign(nrcomp, -1);
        mv.assign(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 i : mv) distdfs(i, -1, 0);

        md.assign(nrcomp, 1e12);

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

        sort(md.begin(), md.end());

        int mmax = md[nrcomp - 1] + md[nrcomp - 2] + l;
        if (nrcomp != 2) mmax = max(md[nrcomp - 2] + md[nrcomp - 3] + 2*l, mmax);

        return mmax;
    }
};

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