Submission #940194

#	Time	Username	Problem	Language	Result	Execution time	Memory
940194		Der_Vlapos	Dreaming (IOI13_dreaming)	C++17	100 / 100	53 ms	18304 KiB

dreaming

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

using namespace std;

#define f first
#define s second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back

vector<vector<pii>> graph;
vector<int> was;

pii find(int v, int pr = -1)
{
    was[v] = 1;
    pii cur = {0, v};
    for (auto tov : graph[v])
        if (tov.f != pr)
        {
            pii to = find(tov.f, v);
            to.f += tov.s;
            cur = max(cur, to);
        }
    return cur;
}

pii solve(int v, int dpth, int pr = -1)
{
    int cur = 0;
    int res = dpth;
    for (auto tov : graph[v])
        if (tov.f != pr)
        {
            pii to = solve(tov.f, dpth + tov.s, v);
            if (to.f + tov.s > cur)
            {
                cur = to.f + tov.s;
                res = min(to.s, max(dpth, cur));
            }
        }
    return {cur, res};
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    graph.resize(N);
    was.resize(N);
    for (int i = 0; i < M; ++i)
    {
        graph[A[i]].pb({B[i], T[i]});
        graph[B[i]].pb({A[i], T[i]});
    }

    vector<int> d;
    int res = 0;
    for (int i = 0; i < N; ++i)
        if (!was[i])
        {
            int D1 = find(i).s;
            pii cur = solve(D1, 0);
            res = max(res, cur.f);
            d.pb(cur.s);
            // cout << i << " " << D1 << ": " << res.f << " " << res.s << "\n";
        }
    sort(all(d));
    reverse(all(d));
    if (d.size() > 1)
        res = max(res, d[0] + L + d[1]);
    if (d.size() > 2)
        res = max(res, d[1] + L + d[2] + L);

    return res;
}

// #include <stdio.h>
// #include <stdlib.h>
// #include <assert.h>
// #include "dreaming.h"

// #define MAX_N 100000

// static int A[MAX_N];
// static int B[MAX_N];
// static int T[MAX_N];

// int main()
// {
//     int N, M, L, i;

//     assert(scanf("%d%d%d", &N, &M, &L) == 3);
//     for (i = 0; i < M; i++)
//         assert(scanf("%d%d%d", &A[i], &B[i], &T[i]) == 3);

//     int answer = travelTime(N, M, L, A, B, T);
//     printf("%d\n", answer);

//     return 0;
// }

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