Submission #742184

#	Time	Username	Problem	Language	Result	Execution time	Memory
742184		Blagoj	Dreaming (IOI13_dreaming)	C++14	100 / 100	172 ms	21880 KiB

dreaming

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

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

vector<pair<int, int>> g[100005];
vector<int> group;
int mx = 0, ans = 0;
bool visited[100005];

void dfs(int n, int p, int d, vector<pair<int, int>> &path) {
    visited[n] = 1;
    path.push_back({n, d});
    for (auto x : g[n]) {
        if (p != x.first) {
            dfs(x.first, n, d + x.second, path);
        }
    }
}

void solve(int n) {
    vector<pair<int, int>> d, d2;
    dfs(n, -1, 0, d);
    int node, maxDist = -1;
    for (auto x : d) {
        if (x.second > maxDist) {
            maxDist = x.second;
            node = x.first;
        }
    }
    d.clear();
    dfs(node, -1, 0, d);
    map<int, int> mp;
    maxDist = -1;
    for (auto x : d) {
        mp[x.first] = x.second;
        if (x.second > maxDist) {
            maxDist = x.second;
            node = x.first;
        }
    }
    mx = max(mx, maxDist);
    dfs(node, -1, 0, d2);
    for (auto x : d2) {
        ans = min(ans, max(x.second, mp[x.first]));
    }
}

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> groups;
    for (int i = 0; i < N; i++) {
        if (visited[i]) continue;
        ans = INT_MAX;
        solve(i);
        groups.push_back(ans);
    }
    sort(all(groups));
    reverse(all(groups));
    if (groups.size() == 1) return max(groups[0], mx);
    if (groups.size() == 2) return max(groups[0] + groups[1] + L, mx);
    return max({groups[0] + groups[1] + L, groups[1] + groups[2] + 2 * L, mx});
}

Compilation message (stderr)

dreaming.cpp: In function 'void solve(int)':
dreaming.cpp:36:8: warning: 'node' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |     dfs(node, -1, 0, d);
      |     ~~~^~~~~~~~~~~~~~~~

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