Submission #1102869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102869		Zero_OP	Dreaming (IOI13_dreaming)	C++17	100 / 100	81 ms	32916 KiB

dreaming

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

using namespace std;

#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true; return false;
}

template<typename T>
bool maximize(T& a, const T& b){
    if(a < b) return a = b, true; return false;
}

using ll = long long;
using ld = long double;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }

const int MAX = 1e5 + 5;

bool vis[MAX];
int dp_children[MAX], dp_not_children[MAX], dp_diameter[MAX], minBest[MAX];
vector<pair<int, int>> adj[MAX];

void dfs1(int u, int p = -1){
    vis[u] = true;
    for(auto [v, w] : adj[u]) if(v != p){
        adj[v].erase(find(all(adj[v]), make_pair(u, w)));
        dfs1(v);
        maximize(dp_diameter[u], dp_children[v] + w + dp_children[u]);
        maximize(dp_children[u], dp_children[v] + w);
        maximize(dp_diameter[u], dp_diameter[v]);
    }
}

void dfs2(int u, int p = -1){
    minBest[u] = max(dp_children[u], dp_not_children[u]);
    vector<int> pref, suff;
    for(auto [v, w] : adj[u]) if(v != p){
        pref.push_back(dp_children[v] + w);
    }

    suff = pref;

    for(int i = 1; i < sz(pref); ++i){
        pref[i] = max(pref[i - 1], pref[i]);
    }

    for(int i = sz(pref) - 2; i >= 0; --i){
        suff[i] = max(suff[i], suff[i + 1]);
    }

    int i = 0;
    for(auto [v, w] : adj[u]) if(v != p){
        int l = (i > 0 ? pref[i - 1] : 0);
        int r = (i + 1 < sz(suff) ? suff[i + 1] : 0);
        dp_not_children[v] = w + max({dp_not_children[u], l, r});
        ++i;
        dfs2(v);
        minimize(minBest[u], minBest[v]);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    for(int i = 0; i < M; ++i){
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }

    int ans = 0;
    vector<int> r, diamter;
    for(int i = 0; i < N; ++i){
        if(!vis[i]){
            r.push_back(i);
            dfs1(i);
            ans = max(ans, dp_diameter[i]);
        }
    }

    vector<int> solutions;
    fill(vis, vis + N, false);
    for(int rt : r){
        dfs2(rt);
        solutions.push_back(minBest[rt]);
    }

    if(sz(solutions) == 1){
        return ans;
    }

    sort(all(solutions), greater<int>());
    int merge_solutions = 0;
    if(sz(solutions) == 2){
        merge_solutions = L + solutions[0] + solutions[1];
    } else{
        merge_solutions = max(L + solutions[0] + solutions[1], L + solutions[1] + L + solutions[2]);
    }

    return max(merge_solutions, ans);
}

Compilation message (stderr)

dreaming.cpp: In function 'bool minimize(T&, const T&)':
dreaming.cpp:13:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   13 |     if(a > b) return a = b, true; return false;
      |     ^~
dreaming.cpp:13:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   13 |     if(a > b) return a = b, true; return false;
      |                                   ^~~~~~
dreaming.cpp: In function 'bool maximize(T&, const T&)':
dreaming.cpp:18:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |     if(a < b) return a = b, true; return false;
      |     ^~
dreaming.cpp:18:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   18 |     if(a < b) return a = b, true; return false;
      |                                   ^~~~~~

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