Submission #868973

#	Time	Username	Problem	Language	Result	Execution time	Memory
868973		StefanL2005	Dreaming (IOI13_dreaming)	C++14	0 / 100	493 ms	17656 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ll long long
//ifstream in("file.in");

int k = 0;

void DFS_sum(int node, int p, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &Sum, vector<int> &col)
{
    col[node] = k;
    for (int i = 0; i < vec[node].size(); i++)
    {
        int vecin = vec[node][i];
        if (vecin == p)
            continue;

        DFS_sum(vecin, node, vec, cost, Sum, col);
        Sum[node] = max(Sum[node], Sum[vecin] + cost[node][i]);
    }
}

int DFS_Spec(int node, int p, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &down_sum, int &sum1, int &sum2, int &ans)
{
    if (vec[node].size() == 0)
        return 0;
    if (vec[node].size() == 1 && p != -1)
        return ans;

    int path = -1;
    for (int i = 0; i < vec[node].size(); i++)
    {
        int vecin = vec[node][i];
        if (vecin == p)
            continue;

        if (down_sum[vecin] + cost[node][i] == sum1)
        {
            path = i;
            continue;
        }
        if (down_sum[vecin] + cost[node][i] > sum2)
            sum2 = down_sum[vecin] + cost[node][i];
    }

    if (vec[node].size() > 1 && sum2 == 0)
        sum2 = sum1;

    if (p == -1)
        return ans;
    sum1 -= cost[node][path];
    sum2 += cost[node][path];
    
    ans = min(ans, max(sum2, sum1));

    return DFS_Spec(vec[node][path], node, vec, cost, down_sum, sum1, sum2, ans);
}

int graph_hub(int node, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &col)
{
    vector<int> down_sum(vec.size(), 0);
    DFS_sum(node, -1, vec, cost, down_sum, col);

    int sum1 = 0, sum2 = 0;
    
    for (int i = 0; i < vec[node].size(); i++)
        sum1 = max(sum1, down_sum[vec[node][i]] + cost[node][i]);

    int ans = sum1;
    
    return DFS_Spec(node, -1, vec, cost, down_sum, sum1, sum2, ans);
}
int travelTime(int n, int m, int l, int A[], int B[], int C[])
{
    vector<vector<int>> vec(n);
    vector<vector<int>> cost(n);
    vector<int> col(n, -1);
    for (int i = 0; i < m; i++)
    {
        vec[A[i]].push_back(B[i]);
        vec[B[i]].push_back(A[i]);
        cost[A[i]].push_back(C[i]);
        cost[B[i]].push_back(C[i]);     
    }

    if (m == n - 1)
    {
        vector<int> down_sum(vec.size(), 0);
        DFS_sum(0, -1, vec, cost, down_sum, col);
        int sum1 = 0, sum2 = 0;

        for (int i = 0; i < vec[0].size(); i++)
        {
            int S = down_sum[vec[0][i]] + cost[0][i];
            if (S > sum1)
            {
                sum2 = sum1;
                sum1 = S;
            }
            else
                sum2 = max(sum2, S);
        }

        return sum1 + sum2;
    }

    vector<int> L;
    int Max = 0;
    for (int i = 0; i < n; i++)
    {
        if (col[i] == -1)
        {
            int ans = graph_hub(i, vec, cost, col);
            k++;
            Max = max(Max, ans);
            L.push_back(ans);
        }
    }

    pair<int, int> secMax = make_pair(0, 0);
    bool ok = false;
    for (int i = 0; i < L.size(); i++)
    {
        if (L[i] == Max && !ok)
        {
            ok = true;
            continue;
        }

        if (L[i] > secMax.first)
        {
            secMax.second = secMax.first;
            secMax.first = L[i];
        }
        else
            secMax.second = max(secMax.second, L[i]);
    }

    return max(Max + l + secMax.first, secMax.first + l * 2 + secMax.second);
}

/*
int main()
{
    int n, m, l;
    in>> n >> m >> l;
    vector<int> A(m), B(m), C(m);
    for (int i = 0; i < m; i++)
        in>> A[i];
    for (int i = 0; i < m; i++)
        in>> B[i];
    for (int i = 0; i < m; i++)
        in>> C[i];

    cout<< travelTime(n, m, l, A, B, C);
    return 0;
}*/

Compilation message (stderr)

dreaming.cpp: In function 'void DFS_sum(int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<int>&)':
dreaming.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int DFS_Spec(int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&, int&, int&, int&)':
dreaming.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int graph_hub(int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&)':
dreaming.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int i = 0; i < vec[0].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~
dreaming.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |     for (int i = 0; i < L.size(); i++)
      |                     ~~^~~~~~~~~~

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