Submission #1040183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040183		jer033	Dreaming (IOI13_dreaming)	C++17	100 / 100	58 ms	22768 KiB

dreaming

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

int radius(int a, int b, int billy, vector<vector<pair<int, int>>> (&edges), vector<int> (&nodes_in_cc), vector<pair<int, int>> (&parent), vector<vector<pair<int, int>>> (&children), vector<vector<pair<int, int>>> (&going_up), vector<int> (&cc))
{
    vector<int> patha;
    vector<int> pathb;
    patha.push_back(a);
    int c = a;
    while (c!=billy)
    {
        c = parent[c].first;
        patha.push_back(c);
    }
    pathb.push_back(b);
    int d = b;
    while (d!=billy)
    {
        d = parent[d].first;
        pathb.push_back(d);
    }
    int las = billy;
    int e = patha.size();
    int f = pathb.size();
    while ((e>0) and (f>0) and (patha[e-1]==pathb[f-1]))
    {
        las = patha[e-1];
        patha.pop_back();
        pathb.pop_back();
        e--;
        f--;
    }
    patha.push_back(las);
    pathb.push_back(las);
    e = patha.size();
    f = pathb.size();
    vector<int> all_path;
    for (int i=0; i<(e-1); i++)
    {
        all_path.push_back(parent[patha[i]].second);
    }
    for (int i=f-2; i>=0; i--)
    {
        all_path.push_back(parent[pathb[i]].second);
    }
    int k = all_path.size();
    vector<int> partial_sums;
    int p = 0;
    partial_sums.push_back(0);
    for (int i=0; i<k; i++)
    {
        p += all_path[i];
        partial_sums.push_back(p);
    }
    int answer = p+1;
    for (int q: partial_sums)
    {
        int score = max(p-q, q);
        answer = min(answer, score);
    }
    return answer;
}

int diameter_big = 0;
int tree_radius(int billy, vector<vector<pair<int, int>>> (&edges), vector<int> (&nodes_in_cc), vector<pair<int, int>> (&parent), vector<vector<pair<int, int>>> (&children), vector<vector<pair<int, int>>> (&going_up), vector<int> (&cc))
{
    int best_dia = 0;
    int best_node_a = billy;
    int best_node_b = billy;
    int siz = nodes_in_cc.size();
    for (int ind = siz-1; ind>=0; ind--)
    {
        vector<pair<int, int>> choices = going_up[nodes_in_cc[ind]];
        //for (pair<int, int> x : choices)
            //cout << x.first << ' ' << x.second << '\n';
        sort(choices.begin(), choices.end(), greater<>());
        if ((choices.size())>=2)
        {
            int candidate_length = choices[0].first + choices[1].first;
            if (candidate_length > best_dia)
            {
                best_dia = candidate_length;
                best_node_a = choices[0].second;
                best_node_b = choices[1].second;
            }
        }
        if ((choices.size())>=1)
        {
            int candidate_length = choices[0].first;
            if (candidate_length > best_dia)
            {
                best_dia = candidate_length;
                best_node_a = choices[0].second;
                best_node_b = nodes_in_cc[ind];
            }
        }
        if (ind>0)
        {
            int tatay = parent[nodes_in_cc[ind]].first;
            int bigat = parent[nodes_in_cc[ind]].second;
            pair<int, int> inheri;
            if ((choices.size())>=1)
            {
                inheri = {choices[0].first + bigat, choices[0].second};
            }
            else
            {
                inheri = {bigat, nodes_in_cc[ind]};
            }
            going_up[tatay].push_back(inheri);
        }
    }
    diameter_big = max(diameter_big, best_dia);
    return radius(best_node_a, best_node_b, billy, edges, nodes_in_cc, parent, children, going_up, cc);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    diameter_big = 0;
    vector<vector<pair<int, int>>> edges(N);
    for (int i=0; i<M; i++)
    {
        edges[A[i]].push_back({B[i], T[i]});
        edges[B[i]].push_back({A[i], T[i]});
    }
    vector<int> cc(N, -1);
    vector<pair<int, int>> parent(N, {-2, 0});
    vector<vector<pair<int, int>>> children(N);
    vector<vector<pair<int, int>>> going_up(N);//The vector contains one pair for each child. The pair contains {deepest depth, deepest descendant}.
    vector<int> hubs;
    hubs.reserve(N);

    for (int billy = 0; billy < N; billy++)//billabong is such a long word
        if (cc[billy] == -1)
        {
            vector<int> nodes_in_cc;
            cc[billy] = billy;
            parent[billy] = {-1, 0};
            nodes_in_cc.push_back(billy);
            int next_ind = 0;
            int end_ind = 1;
            while (next_ind < end_ind)
            {
                int curr_node = nodes_in_cc[next_ind];
                next_ind++;
                for (pair<int, int> edg: edges[curr_node])
                {
                    int neighbor = edg.first;
                    int weight = edg.second;
                    if (cc[neighbor] == -1)
                    {
                        cc[neighbor] = billy;
                        parent[neighbor] = {curr_node, weight};
                        children[curr_node].push_back(edg);
                        nodes_in_cc.push_back(neighbor);
                        end_ind++;
                    }
                }
            }
            hubs.push_back(tree_radius(billy, edges, nodes_in_cc, parent, children, going_up, cc));
        }

    int hsize = hubs.size();
    //for (int i=0; i<hsize; i++)
        //cout << hubs[i] << '\n';
    if (hsize == 1)
    {
        return diameter_big;
    }
    sort(hubs.begin(), hubs.end(), greater());
    for (int i=1; i<hsize; i++)
        hubs[i] += L;
    sort(hubs.begin(), hubs.end(), greater());
    int proposed_answer = hubs[0]+hubs[1];
    return max(proposed_answer, diameter_big);
}

/*int main()
{
    int N, M, L;
    cin >> N >> M >> L;
    int A[M];
    int B[M];
    int T[M];
    for (int i=0; i<M; i++)
        cin >> A[i] >> B[i] >> T[i];
    cout << travelTime(N, M, L, A, B, T) << '\n';
}*/

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