Submission #491982

#	Time	Username	Problem	Language	Result	Execution time	Memory
491982		TheScrasse	Dreaming (IOI13_dreaming)	C++17	18 / 100	47 ms	16368 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 100010

ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll nw, w, vis[maxn], dist[maxn];
array<ll, 2> o;
vector<ll> v;
vector<array<ll, 2>> adj[maxn];

void dfs(ll ty, ll s) {
    // cout << "dfs" _ ty _ s << nl;
    vis[s] = ty;
    for (auto [u, w] : adj[s]) {
        if (vis[u] == ty) continue;
        if (ty == 3) o = min(o, {max(dist[u], dist[s] + w), u});
        else o = max(o, {dist[s] + w, u});
        dist[u] = dist[s] + w;
        // cout << "o =" _ o[0] _ o[1] << nl;
        dfs(ty, u);
    }
}

ll diam(ll s) {
    ll i, a, b;

    o = {0, s}; dist[s] = 0; dfs(1, s); a = o[1];
    o = {0, a}; dist[a] = 0; dfs(2, a); b = o[1];
    if (m == n - 1) return o[0];
    dist[b] = 0; dfs(3, b); return o[0];
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N; m = M; nw = L;
    for (i = 1; i <= n; i++) {
        a = A[i - 1] + 1; b = B[i - 1] + 1; w = T[i - 1];
        adj[a].pb({b, w}); adj[b].pb({a, w});
    }

    for (i = 1; i <= n; i++) {
        if (vis[i] != 0) continue;
        v.pb(diam(i));
    }

    /* for (auto u : v) cout << u << ' ';
    cout << nl; */

    sort(v.begin(), v.end()); reverse(v.begin(), v.end());
    res = 0;

    if (m == n - 1) res = max(res, v[0]);
    if (m <= n - 2) res = max(res, v[0] + v[1] + nw);
    if (m <= n - 3) res = max(res, v[1] + v[2] + 2 * nw);

    return res;
}

Compilation message (stderr)

dreaming.cpp: In function 'long long int diam(long long int)':
dreaming.cpp:36:8: warning: unused variable 'i' [-Wunused-variable]
   36 |     ll i, a, b;
      |        ^

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