Submission #708171

#	Time	Username	Problem	Language	Result	Execution time	Memory
708171		finn__	Dreaming (IOI13_dreaming)	C++17	100 / 100	136 ms	20724 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

constexpr size_t N = 100000;

vector<pair<size_t, size_t>> g[N];
size_t f[N][2], c[N];
bitset<N> visited;

void update_state(size_t u, size_t d, size_t v)
{
    if (d >= f[u][0])
        f[u][1] = f[u][0], f[u][0] = d, c[u] = v;
    else if (d > f[u][1])
        f[u][1] = d;
}

void calc1(size_t u)
{
    f[u][0] = f[u][1] = 0;
    c[u] = SIZE_MAX;
    visited[u] = 1;

    for (auto const &[v, w] : g[u])
        if (!visited[v])
        {
            calc1(v);
            update_state(u, f[v][0] + w, v);
        }
}

void calc2(size_t u, size_t p)
{
    for (auto const &[v, w] : g[u])
        if (v != p)
        {
            if (v == c[u])
                update_state(v, f[u][1] + w, u);
            else
                update_state(v, f[u][0] + w, u);
            calc2(v, u);
        }
}

size_t find_min_max(size_t u, size_t p)
{
    size_t ans = max(f[u][0], f[u][1]);
    for (auto const &[v, w] : g[u])
        if (v != p)
            ans = min(ans, find_min_max(v, u));
    return ans;
}

size_t find_diameter(size_t u, size_t p)
{
    size_t ans = f[u][0] + f[u][1];
    for (auto const &[v, w] : g[u])
        if (v != p)
            ans = max(ans, find_diameter(v, u));
    return ans;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
    for (size_t i = 0; i < m; i++)
    {
        g[a[i]].emplace_back(b[i], t[i]);
        g[b[i]].emplace_back(a[i], t[i]);
    }

    vector<int> distances;
    int max_diameter = 0;
    for (size_t i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            calc1(i);
            calc2(i, SIZE_MAX);
            distances.push_back(find_min_max(i, SIZE_MAX) + l);
            max_diameter = max<int>(max_diameter, find_diameter(i, SIZE_MAX));
        }
    }
    sort(distances.begin(), distances.end(), greater<int>());
    if (distances.size() >= 2)
        max_diameter = max(max_diameter, distances[0] + distances[1] - l);
    if (distances.size() >= 3)
        max_diameter = max(max_diameter, distances[1] + distances[2]);
    return max_diameter;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:66:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     for (size_t i = 0; i < m; i++)
      |                        ~~^~~
dreaming.cpp:74:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~

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