Submission #1075658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075658		shmax	Dreaming (IOI13_dreaming)	C++17	0 / 100	39 ms	18296 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

template<typename T>
using vec = vector<T>;

int travelTime(int n, int M, int L, int A[], int B[], int T[]) {
    vec<vec<pair<int, int>>> g(n);
    for (int i = 0; i < M; i++) {
        g[A[i]].emplace_back(B[i], T[i]);
        g[B[i]].emplace_back(A[i], T[i]);
    }
    vec<bool> used(n);
    vec<int> diam;
    struct Val {
        int max_diam;
        int d_v;
        int d_u;
        int max_depth;
        int v_depth;
    };
    function<Val(int, int)> dfs = [&](int v, int p) -> Val {
        used[v] = true;
        Val cur = {0, v, v, 0, v};
        int t1 = 0, t2 = 0;
        int v1 = v, v2 = v;
        for (auto [u, w]: g[v]) {
            if (u == p) continue;
            Val nxt = dfs(u, v);
            if (cur.max_depth < nxt.max_depth + w) {
                cur.max_depth = nxt.max_depth + w;
                cur.v_depth = nxt.v_depth;
            }
            if (t1 < nxt.max_depth + w) {
                t2 = t1;
                v2 = v1;
                t1 = nxt.max_depth + w;
                v1 = nxt.v_depth;
            } else if (t2 < nxt.max_depth + w) {
                t2 = nxt.max_depth + w;
                v2 = nxt.v_depth;
            }
            if (cur.max_diam < nxt.max_diam) {
                cur.max_diam = nxt.max_diam;
                cur.d_v = nxt.d_v;
                cur.d_u = nxt.d_u;
            }
        }
        if (cur.max_diam < t1 + t2) {
            cur.max_diam = t1 + t2;
            cur.d_v = v1;
            cur.d_u = v2;
        }
        return cur;
    };

    auto build = [&](int v) {
        if (used[v]) return;
        Val cur = dfs(v, -1);
        vec<int> edges;
        function<bool(int, int)> dfs1 = [&](int v, int p) {
            if (v == cur.d_u) return true;
            for (auto [u, w]: g[v]) {
                if (u == p) continue;
                if (dfs1(u, v)) {
                    edges.push_back(w);
                    return true;
                }
            }
            return false;
        };
        dfs1(cur.d_v, -1);
        int sum = accumulate(edges.begin(), edges.end(), 0);
        int cur_sum = 0;

        for (int i = 0; i < edges.size(); i++) {
            if ((cur_sum + edges[i]) * 2 >= sum) {
                int var1 = sum - cur_sum;
                int var2 = cur_sum + edges[i];
                diam.push_back(min(var1, var2));
                return;
            } else {
                cur_sum += edges[i];
            }
        }

    };

    for (int i = 0; i < n; i++)
        build(i);

    sort(diam.rbegin(), diam.rend());
    if (diam.size() == 1) {
        return diam[0];
    }
    if (diam.size() == 2) {
        return diam[0] + diam[1] + L;
    }
    if (diam.size() >= 3) {
        return max(diam[0] + diam[1] + L, diam[1] + diam[2] + 2 * L);
    }

}

Compilation message (stderr)

dreaming.cpp: In lambda function:
dreaming.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for (int i = 0; i < edges.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:10:33: warning: control reaches end of non-void function [-Wreturn-type]
   10 |     vec<vec<pair<int, int>>> g(n);
      |                                 ^

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