Submission #156339

#	Time	Username	Problem	Language	Result	Execution time	Memory
156339		Alexa2001	Dreaming (IOI13_dreaming)	C++17	42 / 100	119 ms	15348 KiB

dreaming

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

using namespace std;

const int Nmax = 1e5 + 5;

vector<int> dia, mn, nodes;
vector<pair<int,int>> v[Nmax];
int dist[3][Nmax];
bool used[Nmax];

void dfs(int node, int t, int dad = 0)
{
    if(!t) nodes.push_back(node), used[node] = 1;

    for(auto it : v[node])
        if(it.first != dad)
        {
            dist[t][it.first] = dist[t][node] + it.second;
            dfs(it.first, t, node);
        }
}

void solve_comp(int root)
{
    nodes.clear();
    dfs(root, 0);

    int x = root;

    for(auto i : nodes)
        if(dist[0][x] < dist[0][i]) x = i;

    dfs(x, 1);

    int y = x;
    for(auto i : nodes)
        if(dist[1][y] < dist[1][i]) y = i;

    dfs(y, 2);

    int best = 1e9;

    for(auto i : nodes)
        if(dist[1][i] + dist[2][i] == dist[1][y])
            best = min(best, max(dist[1][i], dist[2][i]));

    dia.push_back(dist[1][y]);
    mn.push_back(best);
}

int travelTime(int n, int m, int L, int A[], int B[], int T[])
{
    int ans = 0;
    int i;

    for(i=0; i<m; ++i)
    {
        v[A[i]].push_back({B[i], T[i]});
        v[B[i]].push_back({A[i], T[i]});
    }

    for(i=0; i<n; ++i)
        if(!used[i]) solve_comp(i);

    for(auto it : dia)
        ans = max(ans, it);

    sort(mn.begin(), mn.end());
    reverse(mn.begin(), mn.end());

    if(mn.size() >= 2)
        ans = max(ans, mn[0] + mn[1] + L);

    if(mn.size() >= 3)
        ans = max(ans, mn[1] + mn[2] + 2 * L);

    return ans;
}

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