Submission #436661

#	Time	Username	Problem	Language	Result	Execution time	Memory
436661		erekle	Dreaming (IOI13_dreaming)	C++17	100 / 100	152 ms	17892 KiB

dreaming

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

using namespace std;

vector<vector<pair<int, int>>> g;
vector<bool> seen;

// +++ FINDS DIAMETER OF COMPONENT GIVEN ANY NODE +++
pair<int, int> findFurthest(int v, int parent = -1) { // returns distance, node
    seen[v] = true;
    pair<int, int> furthest{0, v};
    for (pair<int, int> u : g[v]) {
        if (u.first == parent) continue;
        pair<int, int> d = findFurthest(u.first, v);
        d.first += u.second;
        if (d > furthest) furthest = d;
    }
    return furthest;
}

int diameter(int v) {
    pair<int, int> furthest = findFurthest(v);
    return findFurthest(furthest.second).first;
}
// ------------------ END DIAMETER ------------------



vector<int> longest, longestID, secondLongest; // with first move down
int dfs1(int v, int parent = -1) {
    seen[v] = true;
    for (pair<int, int> u : g[v]) {
        if (u.first == parent) continue;
        int d = u.second + dfs1(u.first, v);
        if (d >= longest[v]) {
            secondLongest[v] = longest[v];
            longest[v] = d, longestID[v] = u.first;
        } else if (d > secondLongest[v]) secondLongest[v] = d;
    }
    return longest[v];
}

vector<int> longestFrom;
int dfs2(int v, int bestUp = 0, int parent = -1) {
    seen[v] = true;
    longestFrom[v] = max(longest[v], bestUp);
    int minLongest = longestFrom[v];
    for (pair<int, int> u : g[v]) {
        if (u.first == parent) continue;
        int child;
        if (u.first == longestID[v]) {
            child = dfs2(u.first, u.second + max(secondLongest[v], bestUp), v);
        } else {
            child = dfs2(u.first, u.second + max(longest[v], bestUp), v);
        }
        minLongest = min(minLongest, child);
    }
    return minLongest;
}

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    g.resize(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]);
    }

    // find longest distance from each node
    longest.resize(n), longestID.resize(n, -1), secondLongest.resize(n);
    seen.resize(n);
    for (int i = 0; i < n; ++i) {
        if (!seen[i]) dfs1(i);
    }

    // finish finding longest distances
    // and find smallest longest distance in each component
    vector<int> vals; // gates
    longestFrom.resize(n);
    seen.assign(n, false);
    for (int i = 0; i < n; ++i) {
        if (!seen[i]) vals.push_back(dfs2(i));
    }

    sort(vals.rbegin(), vals.rend());

    int maxD = 0;
    seen.assign(n, false);
    for (int i = 0; i < n; ++i) {
        if (!seen[i]) maxD = max(maxD, diameter(i));
    }
    if (vals.size() >= 2) maxD = max(maxD, vals[0] + L + vals[1]);
    if (vals.size() >= 3) maxD = max(maxD, vals[1] + 2*L + vals[2]);
    return maxD;
}

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