Submission #298625

#	Time	Username	Problem	Language	Result	Execution time	Memory
298625		emil_physmath	Dreaming (IOI13_dreaming)	C++17	100 / 100	113 ms	18680 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 100'000;
#ifdef MANSON
#define BUGO(x) cerr << #x << " = " << x << '\n';
#else
#define BUGO(x)
#endif
struct Jmp {
    int to, w;
    operator int&() { return to; }
};

vector<Jmp> nei[maxN];
bool used[maxN];

void Maxi(auto& l, auto r) { l = max(l, r); }
int dpu[maxN], dpd[maxN];
void DFSD(int v, int par = -1)
{
    used[v] = true;
    for (Jmp& to: nei[v])
        if (to != par) {
            DFSD(to, v);
            dpd[v] = max(dpd[v], dpd[to] + to.w);
        }
}
int diam = 0, farth = maxN;
void DFSU(int v, int par = -1)
{
    if (par == -1) {
        diam = 0;
        farth = 1000'000'000;
    }
    pair<int, int> mx = {0, 0};
    for (Jmp& to: nei[v])
        if (to != par) {
            Maxi(mx.second, dpd[to] + to.w);
            if (mx.second > mx.first) swap(mx.first, mx.second);
        }
    Maxi(diam, mx.first + mx.second);
    farth = min(farth, max(dpd[v], dpu[v]));
    for (Jmp& to: nei[v])
        if (to != par)
        {
            Maxi(dpu[to], max(dpu[v], mx.first == dpd[to] + to.w ? mx.second : mx.first) + to.w);
            DFSU(to, v);
        }
}
int travelTime(int n, int m, int l, int a[], int b[], int w[]) {
    for (int i = 0; i < m; ++i) {
        nei[a[i]].push_back({b[i], w[i]});
        nei[b[i]].push_back({a[i], w[i]});
    }
    vector<int> far;
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (!used[i]) {
            DFSD(i, -1);
            DFSU(i, -1);
            far.push_back(farth);
            Maxi(ans, diam);
            BUGO(i)
            BUGO(diam)
            BUGO(farth)
        }
    sort(far.begin(), far.end(), greater<int>());
    if (far.size() >= 2)
        Maxi(ans, far[0] + l + far[1]);
    if (far.size() >= 3)
        Maxi(ans, far[1] + l + l + far[2]);
    return ans;
}

Compilation message (stderr)

dreaming.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   18 | void Maxi(auto& l, auto r) { l = max(l, r); }
      |           ^~~~
dreaming.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts'
   18 | void Maxi(auto& l, auto r) { l = max(l, r); }
      |                    ^~~~

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