oj.uz

Submission #868974

# Submission time Handle Problem Language Result Execution time Memory
868974 2023-11-02T17:22:49 Z StefanL2005 Dreaming (IOI13_dreaming) C++14
0 / 100
 503 ms 16868 KB 
#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 (path == -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;
    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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 16868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 16868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 10148 KB Output is correct
2 Correct 294 ms 10404 KB Output is correct
3 Correct 293 ms 10160 KB Output is correct
4 Correct 334 ms 10212 KB Output is correct
5 Correct 279 ms 10464 KB Output is correct
6 Correct 313 ms 10932 KB Output is correct
7 Correct 346 ms 10956 KB Output is correct
8 Correct 265 ms 10196 KB Output is correct
9 Correct 294 ms 9960 KB Output is correct
10 Correct 321 ms 10572 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 467 ms 6604 KB Output is correct
13 Correct 463 ms 6348 KB Output is correct
14 Correct 503 ms 6468 KB Output is correct
15 Correct 438 ms 6344 KB Output is correct
16 Correct 436 ms 6456 KB Output is correct
17 Correct 444 ms 6564 KB Output is correct
18 Correct 489 ms 6344 KB Output is correct
19 Correct 429 ms 6608 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Incorrect 1 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 16868 KB Output isn't correct
2 Halted 0 ms 0 KB -