Submission #101862

#	Time	Username	Problem	Language	Result	Execution time	Memory
101862		naoai	Dreaming (IOI13_dreaming)	C++14	100 / 100	117 ms	15732 KiB

dreaming

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

using namespace std;

const int nmax = 1e5;

static int mx, cn;
static bool viz[nmax + 1];
static pair<int, int> tata[nmax + 1];
static vector<pair<int, int>> g[nmax + 1];

void dfs (int nod, int t, int h) {
    viz[nod] = 1;

    if (h > mx) {
        mx = h;
        cn = nod;
    }

    for (auto i : g[nod]) {
        if (i.first != t) {
            dfs(i.first, nod, h + i.second);
            tata[i.first] = {nod, i.second};
        }
    }
}

int cauta (int nod) {
    mx = -1;
    cn = -1;
    dfs(nod, -1, 0);
    return cn;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; ++ i) {
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }

    vector<int> dst;
    int lmax = 0;

    for (int i = 0; i < N; ++ i) {
        if (viz[i] == 0) {
            int c1 = cauta(i);
            cauta(c1);

            int x = cn, aux = mx, lst = 0;
            while (aux > mx / 2) {
                aux -= tata[x].second;
                lst = tata[x].second;
                x = tata[x].first;
            }

            dst.push_back(min(mx - aux, aux + lst));
               // cout << dst.back() << "\n";
            lmax = max(lmax, mx);
        }
    }

    sort(dst.begin(), dst.end());
    reverse(dst.begin(), dst.end());

    int leg = 0;

    if (dst.size() >= 2)
        leg = max(leg, dst[0] + L + dst[1]);
    if (dst.size() >= 3)
        leg = max(leg,dst[1] + dst[2] + 2 * L);

    return max(lmax, leg);
}

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