Submission #962059

#	Time	Username	Problem	Language	Result	Execution time	Memory
962059		danikoynov	Dreaming (IOI13_dreaming)	C++14	10 / 100	1078 ms	12764 KiB

dreaming

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


using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

vector < pair < int, int > > adj[maxn];

int used[maxn], depth[maxn];
int max_depth[maxn];
void calc(int v, int p)
{
    max_depth[v] = 0;
    for (pair < int, int > nb : adj[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        depth[u] = depth[v] + nb.second;
        calc(u, v);
        max_depth[v] = max(max_depth[v], max_depth[u] + nb.second);
    }
}
vector < int > ord;
void trav(int v, int p)
{
    ord.push_back(v);
    used[v] = 1;
    for (pair < int, int > nb : adj[v])
    {
        if (nb.first == p)
            continue;
        trav(nb.first, v);
    }
}

int dist;

void dfs(int v, int p, int lon)
{

    //cout << "dfs " << v << " " << p << " " << lon << endl;
    int val = lon, sec = 0;
    for (pair < int, int > nb : adj[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        if (max_depth[u] + nb.second > val)
        {
            sec = val;
            val = max_depth[u] + nb.second;
        }
        else if (max_depth[u] + nb.second > sec)
        {
            sec = max_depth[u] + nb.second;
        }
    }
    //cout << val << " " << sec << endl;
    dist = min(dist, val);
    if (val == lon)
        return;
    for (pair < int, int > nb : adj[v])
    {
        int u = nb.first;
        if (u == p)
            continue;
        if (val == max_depth[u] + nb.second)
        {
            dfs(u, v, sec + nb.second);
            return;
        }
    }
}
int cap;

int path[maxn];
void bfs(int v)
{
    for (int w : ord)
        path[w] = -1;
    path[v] = 0;
    queue < int > q;
    q.push(v);
    while(!q.empty())
    {
        v = q.front();
        q.pop();
        for (pair <int, int > nb : adj[v])
        {
            if (path[nb.first] == -1)
            {
                path[nb.first] = path[v] + nb.second;
                q.push(nb.first);
            }
        }
    }
}
int find_distance(int v)
{
    ord.clear();
    trav(v, -1);
    int dist = 2e9;
    for (int w : ord)
    {
        calc(w, -1);
        dist = min(dist, max_depth[w]);
    }
    bfs(v);
    int ds = v;
    for (int u : ord)
        if (path[u] > path[ds])
            ds = u;
    bfs(ds);
    for (int u : ord)
        if (path[u] > cap)
            cap = path[u];
    return dist;
}


int travelTime(int N, int M, int L, int A[], int B[], int T[])
{

    for (int i = 0; i < M; i ++)
    {
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }

    //cout << find_distance(1) << endl;
    //exit(0);
    vector < int > values;
    for (int i = 0; i < N; i ++)
    {
        if (!used[i])
            values.push_back(find_distance(i));
    }


    //for (int cur : values)
    //cout << cur << " ";
    //cout << endl;
    sort(values.begin(), values.end());

    int sz = values.size();
    int res = values[sz - 1] + values[sz - 2] + L;
    if (sz >= 3)
        res = max(res, values[sz - 2] + values[sz - 3] + 2 * L);
    res = max(res, cap);
    return res;
}

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