Submission #1209787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209787		LIA	Dreaming (IOI13_dreaming)	C++17	0 / 100	58 ms	8512 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
const ll inf = 1e9 + 7;
vvpll g;
ll sum1 = 0, sum2 = 0;
ll max_to_node_1 = inf, max_to_node_2 = inf;
vb vis;

void dfs_1(ll node, ll) {
    stack<ll> st;
    st.push(node);
    vis[node] = true;
    while (!st.empty()) {
        ll u = st.top(); st.pop();
        for (auto [v, w] : g[u]) {
            if (!vis[v]) {
                vis[v] = true;
                sum1 += w;
                st.push(v);
            }
        }
    }
}

void dfs_2(ll node, ll) {
    stack<ll> st;
    st.push(node);
    vis[node] = true;
    while (!st.empty()) {
        ll u = st.top(); st.pop();
        for (auto [v, w] : g[u]) {
            if (!vis[v]) {
                vis[v] = true;
                sum2 += w;
                st.push(v);
            }
        }
    }
}

void calc1(ll node, ll) {
    stack<pair<ll,ll>> st;
    st.push({node,0});
    vis[node] = true;
    while (!st.empty()) {
        auto [u, d] = st.top(); st.pop();
        ll mx = max(d, sum1 - d);
        max_to_node_1 = min(max_to_node_1, mx);
        for (auto [v, w] : g[u]) {
            if (!vis[v]) {
                vis[v] = true;
                st.push({v, d + w});
            }
        }
    }
}

void calc2(ll node, ll) {
    stack<pair<ll,ll>> st;
    st.push({node,0});
    vis[node] = true;
    while (!st.empty()) {
        auto [u, d] = st.top(); st.pop();
        ll mx = max(d, sum2 - d);
        max_to_node_2 = min(max_to_node_2, mx);
        for (auto [v, w] : g[u]) {
            if (!vis[v]) {
                vis[v] = true;
                st.push({v, d + w});
            }
        }
    }
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
    g.clear();
    g.resize(n);
    vll deg(n);
    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]});
        deg[A[i]]++; deg[B[i]]++;
    }

    vis.assign(n, false);
    for (int i = 0; i < n; ++i) if (!vis[i]) { dfs_1(i,0); break; }
    for (int i = 0; i < n; ++i) if (!vis[i]) { dfs_2(i,0); break; }

    vis.assign(n, false);
    for (int i = 0; i < n; ++i) if (deg[i] == 1 && !vis[i]) { calc1(i,0); break; }
    for (int i = 0; i < n; ++i) if (deg[i] == 1 && !vis[i]) { calc2(i,0); break; }

    ll ans = max({sum1, sum2, max_to_node_1 + max_to_node_2 + l});
    return ans;
}

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