oj.uz

Submission #1035287

# Submission time Handle Problem Language Result Execution time Memory
1035287 2024-07-26T08:51:11 Z ProtonDecay314 Dreaming (IOI13_dreaming) C++17
18 / 100
 35 ms 9920 KB 
#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;
    }
};

ll 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;
}

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;

    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?
        ll shortest = find_shortest(i, n, m, l, adj, vis, vis2, x1dist, prev);
        comp_costs.pb(shortest);
        // cout << shortest << endl;
    }

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

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

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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 9920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 9920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7884 KB Output is correct
2 Correct 22 ms 7912 KB Output is correct
3 Correct 26 ms 7876 KB Output is correct
4 Correct 24 ms 7876 KB Output is correct
5 Correct 25 ms 7748 KB Output is correct
6 Correct 25 ms 8784 KB Output is correct
7 Correct 22 ms 8140 KB Output is correct
8 Correct 24 ms 7548 KB Output is correct
9 Correct 27 ms 7620 KB Output is correct
10 Correct 24 ms 8128 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 11 ms 6092 KB Output is correct
13 Correct 12 ms 6152 KB Output is correct
14 Correct 11 ms 6092 KB Output is correct
15 Correct 12 ms 6228 KB Output is correct
16 Correct 12 ms 6092 KB Output is correct
17 Correct 14 ms 6344 KB Output is correct
18 Correct 12 ms 6224 KB Output is correct
19 Correct 12 ms 6224 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 12 ms 6232 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 9920 KB Output isn't correct
2 Halted 0 ms 0 KB -