Submission #1179068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179068		vicvic	Dreaming (IOI13_dreaming)	C++20	100 / 100	52 ms	15432 KiB

dreaming

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include "dreaming.h"
using namespace std;
const int NMAX=1e5;
vector <pair <int, int>> vec[NMAX+5];
vector <pair <int, int>> comp;
int viz[NMAX+5], root, diameter, radius, depth[NMAX+5];
void dfs (int nod, int tatal, int d, bool dif)
{
    viz[nod]=1;
    if (d >= diameter)
    {
        diameter = d;
        root = nod;
    }
    if (dif)
    {
        radius=min (radius, max(d, depth[nod]));
    }
    else depth[nod] = d;
    for (auto adj : vec[nod])
    {
        if (adj.first==tatal)
            continue;
        dfs (adj.first, nod, d+adj.second, dif);
    }
}
int travelTime (int n, int m, int l, int *a, int *b, int *c)
{
    int ret=0;
    for (int i=0;i<m;i++)
    {
        vec[a[i]].push_back ({b[i], c[i]});
        vec[b[i]].push_back ({a[i], c[i]});
    }
    for (int i=0;i<n;i++)
    {
        if (viz[i])
            continue;
        diameter=0;
        radius=2e9;
        dfs (i, -1, 0, 0);
        dfs (root, -1, 0, 0);
        dfs (root, -1, 0, 1);
        comp.push_back ({radius, diameter});
    }
    sort (comp.begin(), comp.end(), greater <pair <int, int>> ());
    ret=max (ret, comp[0].second);
    if (comp.size()>=2) ret=max (ret, comp[0].first+comp[1].first+l);
    if (comp.size()>=3) ret=max (ret, comp[1].first+comp[2].first+2*l);
    return ret;
}

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