Submission #962147

#	Time	Username	Problem	Language	Result	Execution time	Memory
962147		NValchanov	Dreaming (IOI13_dreaming)	C++17	47 / 100	101 ms	21448 KiB

dreaming

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

using namespace std;

typedef long long ll;

const ll MAXN = 1e5 + 10;
const ll INF = 4e18 + 10;

struct edge
{
    ll u,v,cost;
    edge(){};
    edge(ll _u, ll _v, ll _cost)
    {
        u = _u;
        v = _v;
        cost = _cost;
    }
    edge(ll _v, ll _cost)
    {
        u = v = _v;
        cost = _cost;
    }

    bool operator<(const edge&e)const
    {
        return cost < e.cost;
    }
};

ll n,m,l;
vector < edge > adj[MAXN];
bool visited[MAXN];
ll len[MAXN];
ll opt1[MAXN];
ll opt2[MAXN];
ll real_distance;
ll border;
vector < ll > topo;

void dfs(ll u, ll par)
{
    topo.push_back(u);
    visited[u] = true;
    for(edge e : adj[u])
        if(e.v != par)
            dfs(e.v, u);
}

void find_opt(ll u, ll par)
{
    opt1[u] = 0;

    for(edge e : adj[u])
    {
        ll v = e.v;
        ll cost = e.cost;

        if(v == par)
            continue;

        find_opt(v, u);

        ll cur = opt1[v] + cost;

        if(cur > opt1[u])
        {
            opt2[u] = opt1[u];
            opt1[u] = cur;
        }
        else
        {
            opt2[u] = max(opt2[u], cur);
        }
    }
}

void find_dist(ll u, ll par, ll carry)
{
    ll cur = max(carry, opt1[u]);

    real_distance = min(real_distance, cur);

    if(carry >= opt1[u])
        return;

    for(edge e : adj[u])
    {
        ll v = e.v;
        ll cost = e.cost;

        if(v == par)
            continue;

        if(opt1[u] == opt1[v] + e.cost)
        {
            ll new_carry = max(carry, opt2[u]) + cost;
            find_dist(v, u, new_carry);
            return; /// prawa rekursiq !!!
        }
    }
}

void find_path(ll src)
{
    for(ll u : topo)
    {
        len[u] = INF;
    }

    len[src] = 0;

    queue < ll > q;
    q.push(src);

    while(!q.empty())
    {
        ll u = q.front();
        q.pop();

        for(edge e : adj[u])
        {
            ll v = e.v;
            ll cost = e.cost;

            if(len[v] == INF) /// unvisited
            {
                len[v] = len[u] + cost;
                q.push(v);
            }
        }
    }
}

void init(ll u)
{
    topo.clear();
    dfs(u, u);
    real_distance = INF;
    find_opt(u, u);
    find_dist(u, u, 0);
    find_path(u);
}

ll solve(ll u)
{
    init(u);

    ll opt_ver = u;

    for(ll v : topo)
        if(len[v] > len[opt_ver])
            opt_ver = v;

    find_path(opt_ver);

    for(ll v : topo)
        if(len[v] > border)
            border = len[v];

    return real_distance;
}

ll solution()
{
    vector < ll > dists;
    for(int i = 0; i < n; i++)
    {
        if(!visited[i])
        {
            ll cur_dist = solve(i);
            dists.push_back(cur_dist);
        }
    }
    sort(dists.begin(), dists.end());

    ll comp_cnt = dists.size();

    ll ans = dists[comp_cnt - 1] + dists[comp_cnt - 2] + l;

    if(comp_cnt >= 3)
    {
        ans = max(ans, dists[comp_cnt - 2] + dists[comp_cnt - 3] + 2 * l);
    }
    ans = max(ans, border);

    return ans;
}

int travelTime(int N, int M, int L, int a[], int b[], int w[])
{
    n = N;
    m = M;
    l = L;

    for(int i = 0; i < m; i++)
    {
        adj[a[i]].push_back(edge(a[i], b[i], w[i]));
        adj[b[i]].push_back(edge(b[i], a[i], w[i]));
    }

    return solution();
}

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