Submission #335966

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
335966	2020-12-14T12:03:15 Z	blue	Dreaming (IOI13_dreaming)	C++11	Compilation error	0 ms	0 KB

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

*/

//complete redo


vector<int> edge[100001];
vector<int> weight[100001];
vector<int> edge_size(1e5 + 1, 0);
vector<int> maxdist(1e5 + 1, 0);
vector<int> visit(1e5 + 1, 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[])
{
    for(int i = 0; i < M; i++)
    {
        edge[A[i]].push_back(B[i]);
        weight[A[i]].push_back(T[i]);
        edge_size[A[i]]++;

        edge[B[i]].push_back(A[i]);
        weight[B[i]].push_back(T[i]);
        edge_size[B[i]]++;
    }


    set<distcomp> tbv;
    for(int i = 0; i < N; i++)
    {
        if(edge_size[i] == 1) tbv.insert(distcomp{i});
    }

    int u, v, w;
    int flag;
    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]) continue;
            edge_size[v]--;
            maxdist[v] = max(maxdist[v], maxdist[u] + w);
            flag = 0;
            if(edge_size[v] == 1)
            {
                tbv.insert(distcomp{v});
            }
        }
    }

    for(int i = 0; i < N; i++) if(edge_size[i] == 0)
    {
        roots.push_back(i);
    }

    int res = 0;
    int max1, max2;
    for(int r: roots)
    {
        max1 = 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);
    }

    for(int i = 0; i < roots.size(); i++) roots[i] = -1 * maxdist[roots[i]];
    sort(roots.begin(), roots.end());

    if(roots.size() >= 2) res = max(res, L - roots[0] - roots[1]);
    if(roots.size() >= 3) res = max(res, 2*L - roots[1] - roots[2]);

    int res0 = res;
if(roots.size() >= 2) res0 = max(res0, L - roots[0] - roots[1]);
if(roots.size() >= 3) res0 = max(res0, 2*L - roots[1] - roots[2]);

int res1 = res;
if(roots.size() >= 2) res1 = max(res1, L - roots[0] - roots[2]);
if(roots.size() >= 3) res1 = max(res1, 2*L - roots[0] - roots[2]);

res = min(res, res1);
res = min(res, res2);

    return res;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(int i = 0; i < edge[u].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int i = 0; i < edge[r].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i = 0; i < roots.size(); i++) roots[i] = -1 * maxdist[roots[i]];
      |                    ~~^~~~~~~~~~~~~~
dreaming.cpp:134:16: error: 'res2' was not declared in this scope; did you mean 'res1'?
  134 | res = min(res, res2);
      |                ^~~~
      |                res1