Submission #335205

#	Time	Username	Problem	Language	Result	Execution time	Memory
335205		blue	Dreaming (IOI13_dreaming)	C++17	0 / 100	90 ms	14188 KiB

dreaming

#include "dreaming.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;

vector<int> edge[100001];
vector<int> weight[100001];
vector<int> maxdist(100001, 0);
vector<int> children(100001, 0);
vector<int> visit(100001, 0);
vector<int> roots;

struct distcomp
{
    int i;
};

bool operator < (distcomp a, distcomp b)
{
    if(maxdist[a.i] == maxdist[b.i]) return a.i < b.i;
    return maxdist[a.i] < maxdist[b.i];
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
//number of nodes, number of edges, common length, edge A[i]-A[i] with length T[i]
{
    for(int i = 0; i < M; i++)
    {
        edge[A[i]].push_back(B[i]);
        weight[A[i]].push_back(T[i]);
        edge[B[i]].push_back(A[i]);
        weight[B[i]].push_back(T[i]);
    }

    //set<int, distcomp> tbv;
    set<distcomp> tbv;
    for(int i = 0; i < N; i++)
    {
        if(edge[i].size() == 1) tbv.insert(distcomp{i});
        if(edge[i].size() == 0) roots.push_back(i);
    }

    int u, v, w;
    while(!tbv.empty())
    {
        u = tbv.begin()->i;
        tbv.erase(tbv.begin());
        visit[u] = 1;


        for(int i = 0; i < edge[u].size(); i++)
        {
            v = edge[u][i];
            w = weight[u][i];

            if(!visit[v])
            {
                children[v]++;
                maxdist[v] = max(maxdist[v], maxdist[u] + w);
                if(children[v] >= edge[v].size() - 1) tbv.insert(distcomp{v});
            }
        }
        if(edge[u].size() == children[u]) roots.push_back(u);
    }
    int res = 0;
    for(int r: roots)
    {
        int max1 = 0, max2 = 0;
        if(edge[r].size() <= 1) continue;
        for(int i = 0; i < edge[r].size(); i++)
        {
            v = edge[r][i];
            w = weight[r][i];
            if(maxdist[v] + w >= max1)
            {
                max2 = max1;
                max1 = maxdist[v] + w;
            }
            else if(maxdist[v] + w >= max2)
            {
                max2 = maxdist[v] + w;
            }
        }
        res = max(res, max1 + max2);
    }
    //cout << res << '\n';
    if(M == N-1) return res;
    else
    {
        for(int i = 0; i < roots.size(); i++) roots[i] = maxdist[roots[i]];
        sort(roots.begin(), roots.end());
        res = max(res, roots[roots.size() - 2] + L + roots[roots.size() - 1]);
        if(roots.size() >= 3) res = max(res, roots[roots.size() - 2] + 2*L + roots[roots.size() - 3]);
    }
    return res;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:54:26: 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 < edge[u].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:63:32: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                 if(children[v] >= edge[v].size() - 1) tbv.insert(distcomp{v});
dreaming.cpp:66:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   66 |         if(edge[u].size() == children[u]) roots.push_back(u);
dreaming.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = 0; i < edge[r].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int i = 0; i < roots.size(); i++) roots[i] = maxdist[roots[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