Submission #686585

#	Time	Username	Problem	Language	Result	Execution time	Memory
686585		saayan007	Dreaming (IOI13_dreaming)	C++17	0 / 100	49 ms	17976 KiB

dreaming

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

using ll = long long;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vl = vector<long long>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;

#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first 
#define sc second
#define mp make_pair
#define pb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void set_ht(ll cur, ll src, vpl &ht, vpl adj[], vl &par, ll rep) {
    par[cur] = rep;
    ht[cur] = {0, 0};
    for(auto [ch, wt] : adj[cur]) {
        if(ch == src)
            continue;
        set_ht(ch, cur, ht, adj, par, rep);
        if(ht[ch].fr + wt > ht[cur].fr) {
            ht[cur].sc = ht[cur].fr;
            ht[cur].fr = ht[ch].fr + wt;
        } else if(ht[ch].fr + wt > ht[cur].sc) {
            ht[cur].sc = ht[ch].fr + wt;
        }
    }
}

void set_tm(ll cur, ll src, vpl &ht, vpl adj[], vl &tm) {
    tm[cur] = ht[cur].fr;
    // cout << cur << ' ' << ht[cur].fr << nl;
    // ll mx = -1;
    // ll sm = -1;
    // for(auto [ch, wt] : adj[cur]) {
        // if(ch == src)
            // continue;
        // if(wt > mx) {
            // sm = mx;
            // mx = wt;
        // } else if(wt > sm) {
            // sm = wt;
        // }
    // }

    for(auto [ch, wt] : adj[cur]) {
        if(ch == src)
            continue;

        ll use = ht[cur].fr;
        if(ht[ch].fr + wt == ht[cur].fr) {
            use = ht[cur].sc;
        }

        pl store = ht[ch];
        if(use + wt > ht[ch].fr) {
            ht[ch].sc = ht[ch].fr;
            ht[ch].fr = use + wt;
        } else if(use + wt > ht[ch].sc) {
            ht[ch].sc = use + wt;
        }
        set_tm(ch, cur, ht, adj, tm);
        ht[ch] = store;
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vl par(N, -1);
    vl tm(N, -1);
    vpl ht(N, {-1, -1});
    vpl adj[N];
    fur(i, 0, M - 1) {
        adj[A[i]].pb(B[i], T[i]);
        adj[B[i]].pb(A[i], T[i]);
    }

    fur(i, 0, N - 1) {
        if(par[i] == -1) {
            set_ht(i, -1, ht, adj, par, i);
            set_tm(i, -1, ht, adj, tm);
        }
    }

    vl times(N, 1e15L);
    fur(i, 0, N - 1) {
        times[par[i]] = min(times[par[i]], tm[i]);
    }
    
    ll mx = -1;
    ll sm = -1;
    fur(i, 0, N - 1) {
        if(par[i] == i) {
            if(times[i] > mx) {
                sm = mx;
                mx = times[i];
            } else if(times[i] > sm) {
                sm = times[i];
            }
        }
    }

    return mx + sm + L;
}

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