Submission #962056

#	Time	Username	Problem	Language	Result	Execution time	Memory
962056		danikoynov	꿈 (IOI13_dreaming)	C++14	0 / 100	27 ms	12040 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)
{
    used[v] = 1;
    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);
    }
}

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 find_distance(int v)
{
    calc(v, -1);
    dist = 2e9;
    dfs(v, -1, 0);
    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 < ll > 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();
    ll res = values[sz - 1] + values[sz - 2] + L;
    if (sz >= 3)
        res = max(res, values[sz - 2] + values[sz - 3] + 2 * L);
    return res;
}

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