Submission #335970

#	Time	Username	Problem	Language	Result	Execution time	Memory
335970		arujbansal	Dreaming (IOI13_dreaming)	C++17	100 / 100	201 ms	25444 KiB

dreaming

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

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
using namespace std;

const int MAXN = 1e5 + 5, INF = 1e9 + 5;
using ll = long long;

struct Edge {
    int u, v, w;

    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
};

vector<vector<pair<int, int>>> g, gComp;
vector<pair<int, int>> bestComps;
vector<vector<Edge>> components;
bool vis[MAXN];
pair<int, int> leaf[2];
int mx;
pair<int, int> optimalRoot;
int diameterDist[MAXN][2];

// Find the nodes in this tree in the forest
void dfs(int u, int p) {
    vis[u] = true;

    if (p == -1) {
        components.back().emplace_back(u, u, 0);
    }

    for (const auto &[v, wt] : g[u]) {
        if (vis[v]) continue;
        dfs(v, u);
        components.back().emplace_back(u, v, wt);
    }
}

void diameter(vector<vector<pair<int, int>>> &graph, int u, int p, int dist, int idx) {
    leaf[idx] = max(leaf[idx], make_pair(dist, u));
    diameterDist[u][idx] = dist;

    optimalRoot = min(optimalRoot, make_pair(max(diameterDist[u][0], diameterDist[u][1]), u));

    for (const auto &[v, wt] : g[u]) {
        if (v == p) continue;
        diameter(graph, v, u, dist + wt, idx);
    }
}

// Find the centre of the weighted tree
void findRoot(int idx) {
    // cout << "####### COMPONENT NUMBER: " << idx + 1 << " ##########\n";

    // Setup the graph for the tree in the forest
    for (const auto &[u, v, wt] : components[idx]) {
        gComp[u].emplace_back(v, wt);
        gComp[v].emplace_back(u, wt);
        // cout << u << " " << v << "\n";
    }

    // cout << "\n";

    // Root the tree at the first node in the component
    int curRoot = components[idx].front().u;

    leaf[0] = leaf[1] = {-INF, -INF};

    // Find the farthest point from the asummed root
    diameter(gComp, curRoot, -1, 0, 0);
    
    // Find the other leaf of the diameter, compute distances to each node from the first leaf of the diaemeter
    diameter(gComp, leaf[0].second, -1, 0, 1);

    // Compute distances to each node from the second leaf of the diameter
    optimalRoot = {INF, curRoot};
    diameter(gComp, leaf[1].second, -1, 0, 0);

    // cout << "Diameter distances:\n";
    // for (const auto &[u, v, wt] : components[idx]) {
    //     cout << u << " " << diameterDist[u][0] << " " << diameterDist[u][1] << "\n";
    //     cout << v << " " << diameterDist[v][0] << " " << diameterDist[v][1] << "\n";
    // }

    // cout << "\n";

    // cout << "Optimal Root: " << optimalRoot.second << "\n\n";

    // Clear the tree in forest graph
    for (const auto &[u, v, wt] : components[idx]) {
        gComp[u].clear();
        gComp[v].clear();
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    g.resize(MAXN);
    gComp.resize(MAXN);

    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 all trees in the forest
    for (int i = 0; i < N; i++) {
        if (vis[i]) continue;
        components.emplace_back();
        dfs(i, -1);
    }

    // Find the weighted centre of each tree in the forest
    for (int i = 0; i < int(components.size()); i++) {
        findRoot(i);

        // optimalRoot --> (max cost to any node, root)
        bestComps.emplace_back(optimalRoot.first, optimalRoot.second);
    }

    // Sort components in non increasing order of weighted centre
    sort(bestComps.begin(), bestComps.end(), greater<>());

    // Root of the tree with maximum weighted centre
    int best = bestComps.front().second;
    
    // cout << "Best: " << best << "\n";

    // Add edges from the maximum weighted centre to the weighted centre of all other trees
    for (int i = 1; i < int(bestComps.size()); i++) {
        // Pair --> (distance, root)
        int v = bestComps[i].second;

        g[best].emplace_back(v, L);
        g[v].emplace_back(best, L);
    }

    leaf[0] = leaf[1] = {-INF, -INF};

    // Find the diameter of the resulting tree
    diameter(g, 0, -1, 0, 0);
    diameter(g, leaf[0].second, -1, 0, 1);

    // Pair --> (diameter, leaf)
    return leaf[1].first;
}

// void solve() {
//     int N, M, L;
//     cin >> N >> M >> L;

//     int A[M], B[M], T[M];
//     for (int i = 0; i < M; i++)
//         cin >> A[i] >> B[i] >> T[i];

//     cout << travelTime(N, M, L, A, B, T) << "\n";
// }

// signed main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);

//     int tc = 1;
//     // cin >> tc;
//     while (tc--) solve();
// }

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