Submission #870086

#	Time	Username	Problem	Language	Result	Execution time	Memory
870086		StefanL2005	Dreaming (IOI13_dreaming)	C++14	59 / 100	1057 ms	22956 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

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

void DFS_main(int node, int p, int main, int sec, vector<int> &sum, int &ans, vector<vector<int>> &vec, vector<vector<int>> &cost)
{
    ans = min(ans, max(main, sec));
    if (sec > main)
        return;
    int nr = 0;
    for (int i = 0; i < vec[node].size(); i++)
    {
        if (vec[node][i] == p)
            continue;
        int temp = sum[vec[node][i]] + cost[node][i];

        if (temp == main)
        {
            nr++;
            continue;
        }
        if (temp > sec && (temp != main || nr >= 1))
            sec = temp; 
    }

    for (int i = 0; i < vec[node].size(); i++)
    {
        if (vec[node][i] == p)
            continue;
        int temp = sum[vec[node][i]] + cost[node][i];

        if (temp == main)
            DFS_main(vec[node][i], node, main - cost[node][i], sec + cost[node][i], sum, ans, vec, cost);
    }
}

int trace(int node, int p, int main, vector<int> &sum, vector<vector<int>> &vec, vector<vector<int>> &cost)
{
    for (int i = 0; i < vec[node].size(); i++)
    {
        if (vec[node][i] == p)
            continue;

        if (sum[vec[node][i]] + cost[node][i] == main)
            return trace(vec[node][i], node, main - cost[node][i], sum, vec, cost);
    }
    
    return node;
}

pair<int, int> graph_hub(int node, vector<vector<int>> &vec, vector<vector<int>> &cost, vector<int> &col)
{
    vector<int> sum(vec.size(), 0);
    DFS_sum(node, -1, sum, vec, cost, col);
    
    int MAX = 0, sec = 0;
    for (int i = 0; i < vec[node].size(); i++)
    {
        int temp = sum[vec[node][i]] + cost[node][i];
 
        if (temp > MAX)
        {
            sec = MAX;
            MAX = temp;
        }
        else
            sec = max(sec, temp);
    }

    int ans = sum[node];
    DFS_main(node, -1, MAX, sec, sum, ans, vec, cost);

    vector<int> new_sum(vec.size(), 0);
    int colt = trace(node, -1, sum[node], sum, vec, cost);
    DFS_sum(colt, -1, new_sum, vec, cost, col);

    return make_pair(ans, new_sum[colt]);
}
int travelTime(int N, int M, int L, int A[], int B[], int C[])
{
    vector<int> col(N, -1);
    vector<vector<int>> vec(N), cost(N);
    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> sum(N, 0);
        DFS_sum(0, -1, sum, vec, cost, col);
        
        int colt = trace(0, -1, sum[0], sum, vec, cost);
        
        vector<int> new_sum(vec.size(), 0);
        DFS_sum(colt, -1, new_sum, vec, cost, col);
        
        return new_sum[colt];
    }

    vector<pair<int, int>> hub_l;
    for (int i = 0; i < N; i++)
        if (col[i] == -1)
        {
            hub_l.push_back(graph_hub(i, vec, cost, col));
            k++;
        }
    
    int unos = 0, dos = 0, tres = 0;

    for (int i = 0; i < hub_l.size(); i++)
    {
        int p = hub_l[i].first;

        if (p > unos)
        {
            tres = dos;
            dos = unos;
            unos = p;
        }
        else
            if (p > dos)
            {
                tres = dos;
                dos = p;
            }
            else
                tres = max(tres, p);
    }
    int Max = 0;
    for (int i = 0; i < hub_l.size(); i++)
        Max = max(Max, hub_l[i].second);
    
    if (M == N - 2)
        return max(unos + L + dos, Max);
    return max(unos + L + dos, max(Max, dos + 2 * L + tres));
}

Compilation message (stderr)

dreaming.cpp: In function 'void DFS_sum(int, int, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&)':
dreaming.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void DFS_main(int, int, int, int, std::vector<int>&, int&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
dreaming.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int trace(int, int, int, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
dreaming.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'std::pair<int, int> graph_hub(int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, std::vector<int>&)':
dreaming.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for (int i = 0; i < vec[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int i = 0; i < hub_l.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
dreaming.cpp:149:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for (int i = 0; i < hub_l.size(); i++)
      |                     ~~^~~~~~~~~~~~~~

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