Submission #919776

#	Time	Username	Problem	Language	Result	Execution time	Memory
919776		Maaxle	Dreaming (IOI13_dreaming)	C++17	47 / 100	59 ms	20052 KiB

dreaming

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

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>

using namespace std;

struct Edge {
    ll node, wth;
};

struct Component {
    ll diameter_length;
    ll rep_max;
};
bool operator < (const Component& a, const Component& b) { return a.rep_max < b.rep_max; }

vector<vector<Edge>> adj;
vector<bool> memo;
pqueue<Component> comp;

ll max_d; ll max_i;
void find_furthest (ll i, ll from, ll cnt) {
    memo[i] = 1;

    if (max_d < cnt) {
        max_d = cnt;
        max_i = i;
    }

    for (auto& k : adj[i]) {
        if (k.node != from) 
            find_furthest(k.node, i, cnt + k.wth);
    }
}

vector<pair<ll, ll>> path;
ll dlength;

ll fill_path (ll i, ll from, ll cnt) {
    path[i].first = cnt;

    ll maxi = 0;
    for (auto& k : adj[i]) {
        if (k.node != from) {
            maxi = max(maxi, k.wth + fill_path(k.node, i, cnt + k.wth));
        }
    }
    path[i].second = maxi;
    dlength = max(dlength, path[i].first + path[i].second);
    return maxi;
}

ll min_abs, rep_i;
void find_rep(ll i, ll from) {
    if (path[i].first + path[i].second == dlength) {
        if (abs(path[i].first - path[i].second) < min_abs) {
            min_abs = abs(path[i].first - path[i].second);
            rep_i = i;
        }
    }

    for (auto& k : adj[i]) {
        if (k.node != from)
            find_rep(k.node, i);
    }
}


Component find_representative(ll i) {
    max_d = -1;
    find_furthest(i, i, 0);
    
    max_d = -1;
    dlength = -1;
    fill_path(max_i, max_i, 0);

    min_abs = INF64;
    find_rep(i, i);

    // cout << dlength << ' ' << max(path[rep_i].first, path[rep_i].second) << '\n';
    return {dlength, max(path[rep_i].first, path[rep_i].second)};
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    adj.resize(N);
    memo.resize(N);
    path.resize(N);
    
    range(i, 0, M) {
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }

    range(i, 0, N) {
        if (!memo[i]) {
            // cout << "** " << i << '\n';
            comp.push(find_representative(i));
        }
    }

    while (comp.size() > 1) {
        Component c1 = comp.top(); comp.pop();
        Component c2 = comp.top(); comp.pop();
        comp.push({max({c1.rep_max + c2.rep_max + L, c1.diameter_length, c2.diameter_length}), max(c1.rep_max, c2.rep_max) + L});
    }

    return comp.top().diameter_length;
}

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