Submission #1035293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035293		ProtonDecay314	Dreaming (IOI13_dreaming)	C++17	100 / 100	80 ms	13176 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)


struct dijkstra_state {
    ll w, c, pr;

    bool operator>(const dijkstra_state& o) const {
        return w > o.w;
    }
};

pll find_shortest(ll s, ll n, ll m, ll l, const vvpll& adj, vb& vis, vb& vis2, vll& x1dist, vll& prev) {
    // Start with s, find the furthest point using Dijkstra's
    // Call the point furthest from s "x1"

    priority_queue<pll, vector<pll>, greater<pll>> q;
    q.push({0ll, s});

    ll x1 = 0ll;

    while(!q.empty()) {
        auto [cd, i] = q.top();
        // cout << "VISITING " << i << endl;
        q.pop();
        if(vis[i]) continue;
        vis[i] = true;
        x1 = i;

        for(auto [j, w] : adj[i]) {
            if(vis[j]) continue;
            q.push({cd + w, j});
        }
    }


    // Find the point furthest from x1. Call it "x2"
    // Make sure that, as you perform your Dijkstra's, you keep track of the previous node
    // Store this in an array somewhere

    priority_queue<dijkstra_state, vector<dijkstra_state>, greater<dijkstra_state>> q2;
    q2.push({0ll, x1, x1});

    ll x2 = 0ll;
    while(!q2.empty()) {
        auto [cd, i, cprev] = q2.top();
        q2.pop();
        if(vis2[i]) continue;
        vis2[i] = true;
        x1dist[i] = cd;
        prev[i] = cprev;
        x2 = i;

        for(auto [j, w] : adj[i]) {
            if(vis2[j]) continue;
            q2.push({cd + w, j, i});
        }
    }

    // Finally, create a prefix array of total prefix distances.
    // Compute the min of max(pref, sum - pref) for all nodes in the path
    ll cur_i_path = x2;

    ll ans = x1dist[cur_i_path];
    ll diameter = ans;

    while(cur_i_path != prev[cur_i_path]) {
        cur_i_path = prev[cur_i_path];

        ans = min(ans, max(x1dist[cur_i_path], diameter - x1dist[cur_i_path]));
    }

    // Return this value, congrats, hard part is done!
    return {ans, diameter};
}

ll solve(ll n, ll m, ll l, const vvpll& adj) {
    vll x1dist(n, -1ll);
    vll prev(n, -1ll);
    vb vis(n, false);
    vb vis2(n, false);
    vll comp_costs;

    ll max_diameter = 0ll;

    for(ll i = 0; i < n; i++) {
        if(vis[i]) continue;

        // If not visited, compute the shortest possible longest shortest path
        // As in, if you pick a node, what is the minimum length of the longest geodesic?
        auto [shortest, diameter] = find_shortest(i, n, m, l, adj, vis, vis2, x1dist, prev);
        comp_costs.pb(shortest);
        max_diameter = max(max_diameter, diameter);
        // cout << shortest << endl;
    }

    sort(comp_costs.begin(), comp_costs.end(), greater<ll>());

    ll c = comp_costs.size();
    if(c == 1ll) return max(comp_costs[0ll], max_diameter);
    else if(c == 2ll) return max(comp_costs[0ll] + comp_costs[1ll] + l, max_diameter);
    else return max(max(comp_costs[0ll] + comp_costs[1ll] + l, comp_costs[1ll] + comp_costs[2ll] + (l << 1ll)), max_diameter);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vvpll adj;

    for(ll i = 0; i < N; i++) {
        vpll adjr;
        adj.pb(adjr);
    }

    for(ll i = 0; i < M; i++) {
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
    }

    return (int)solve(N, M, L, adj);
}

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