Submission #1312627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312627		niwrad	Dreaming (IOI13_dreaming)	C++20	100 / 100	52 ms	20480 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int>>> graph;
vector<vector<pair<int, int>>> dis;
vector<int> vis;
vector<int> sp;

int max_diam = 0;


int dfs(int node, pair<int, int> prev) {
    vis[node] = 1;
    for (auto edge : graph[node]) {
        if (edge.first != prev.first) {
            pair<int, int> check = {edge.second + dfs(edge.first, {node, edge.second}), edge.first};
            if (check > dis[node][0]) {
                swap(check, dis[node][0]);
            }
            if (check > dis[node][1]) {
                swap(check, dis[node][1]);
            } 
        }
    }
    return dis[node][0].first;
}

int dfs1(int node, pair<int, int> prev) {
    if (prev.first != -1) {
        int val = 0;
        int par = prev.first;
        if (dis[par][0].second != node) {
            val = dis[par][0].first + prev.second;
        } else {
            val = dis[par][1].first + prev.second;
        }
        pair<int, int> check = {val, par};
        if (check > dis[node][0]) {
            swap(check, dis[node][0]);
        }
        if (check > dis[node][1]) {
            swap(check, dis[node][1]);
        } 
    }
    max_diam = max(max_diam, dis[node][0].first + dis[node][1].first);
    int mn = dis[node][0].first;
    for (auto edge : graph[node]) {
        if (edge.first != prev.first) {
            mn = min(mn, dfs1(edge.first, {node, edge.second}));
        }
    }
    return mn;
}



int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    graph.resize(N);
    vis.resize(N);
    dis.resize(N, vector<pair<int, int>>(2, {0, -1}));
    for (int i = 0; i < M; i++) {
        graph[A[i]].push_back({B[i], T[i]});
        graph[B[i]].push_back({A[i], T[i]});
    }
    for (int i = 0; i < N; i++) {
        if (!vis[i]) {
            dfs(i, {-1, -1});
            sp.push_back(dfs1(i, {-1, -1}));
        }
    }
    sort(sp.begin(), sp.end(), greater<int>());
    if (sp.size() == 1) {
        return max(sp[0], max_diam);
    } else if (sp.size() == 2) {
        return max(sp[0] + sp[1] + L, max_diam);
    } else {
        return max(max_diam, max(sp[0] + sp[1] + L, sp[1] + sp[2] + 2 * L));
    }
}

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