제출 #335260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335260		blue	Dreaming (IOI13_dreaming)	C++11	65 / 100	176 ms	16876 KiB

dreaming

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

/*
0 --(1)-- 1
          |
         (4)
          |
          4 --(3)-- 5
          |
         (4)
          |
2 --(2)-- 3

Let the root of a connected component be the vertex whose maximum distance from any other vertex in the
connected component is minimum.

All additional edges must be built with both endpoints as roots.

Only one root has more than one additional edge - that with the highest

*/

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]-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);
    }

    int 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});
            }
        }
        bool flag = 0;
        for(int v: edge[u]) if(!visit[v]) flag = 1;
        if(!flag) roots.push_back(u);
        // if(edge[u].size() == children[u])
        // {
        //     //cout << "roots <- " << u << '\n';
        //     roots.push_back(u);
        // }
    }
    int res = 0;
    for(int r: roots)
    {
        int 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(int 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 res;
}

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i = 0; i < edge[u].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:84: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]
   84 |                 if(children[v] >= edge[v].size() - 1) tbv.insert(distcomp{v});
dreaming.cpp:100:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for(int i = 0; i < edge[r].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int 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