Submission #752226

#	Time	Username	Problem	Language	Result	Execution time	Memory
752226		ZeroCool	Dreaming (IOI13_dreaming)	C++14	100 / 100	175 ms	21960 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define inf INT_MAX
using namespace std;

const int mxn = 100005;

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



int findDist(int n) {
    vector<pair<int, int>> d;
    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);
    d.clear();

 
    dfs(node, -1, 0, d);
    int ans = inf;
    for (auto x : d) {
        ans = min(ans, max(x.second, mp[x.first]));
    }
    return ans;
}

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;
        groups.push_back(findDist(i));
    }
    sort(groups.rbegin(),groups.rend());
    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 'int findDist(int)':
dreaming.cpp:37:8: warning: 'node' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |     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