Submission #335252

#	Time	Username	Problem	Language	Result	Execution time	Memory
335252		blue	Dreaming (IOI13_dreaming)	C++11	65 / 100	208 ms	19948 KiB

dreaming

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

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

struct distcomp
{
    long long 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]-B[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);
    }

    long long u, v, w;
    while(!tbv.empty())
    {
        u = tbv.begin()->i;
        tbv.erase(tbv.begin());
        if(visit[u]) continue;
        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])
        {
            //cout << "roots <- " << u << '\n';
            roots.push_back(u);
        }
    }
    long long res = 0;
    for(long long r: roots)
    {
        long long max1 = 0, max2 = 0;
        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';
    for(long long i = 0; i < roots.size(); i++) roots[i] = maxdist[roots[i]]; //*
    sort(roots.begin(), roots.end()); //*
    if(roots.size() >= 2) 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 int(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<long long 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<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long 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<long long int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wsign-compare]
   66 |         if(edge[u].size() == children[u])
dreaming.cpp:76:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i = 0; i < edge[r].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:93:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(long long i = 0; i < roots.size(); i++) roots[i] = maxdist[roots[i]]; //*
      |                          ~~^~~~~~~~~~~~~~

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