Submission #336012

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
336012	2020-12-14T13:29:16 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;

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


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

    int u, v, w;
    int flag, flag2;

    set<distcomp> tbv, tbv2;


    while(!tbv.empty() && !tbv2.empty())
    {
        if(tbv.empty())
        {
            tbv = tbv2;
            tbv2.clear();
        }
        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]--;
            flag = (tbv.find(distcomp{v}) == tbv.end());
            flag2 = (tbv2.find(distcomp{v}) == tbv.end());

            if(flag && flag2) maxdist[v] = max(maxdist[v], maxdist[u] + w);
            else if(flag2)
            {
                tbv.erase(distcomp{v});
                maxdist[v] = max(maxdist[v], maxdist[u] + w);
                tbv.insert(distcomp{v});
            }
            else if(flag)
            {
                tbv2.erase(distcomp{v});
                maxdist[v] = max(maxdist[v], maxdist[u] + w);
                tbv2.insert(distcomp{v});
            }
            if(edge_size[v] <= 1 && !inserted[v])
            {
                tbv2.insert(distcomp{v});
                inserted[v] = 1;
            }
        }
    }

    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] = maxdist[roots[i]] * -1;
    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[1]);

    return res;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:46:13: error: 'tbv' was not declared in this scope
   46 |             tbv.insert(distcomp{i});
      |             ^~~
dreaming.cpp:68:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for(int i = 0; i < edge[u].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:109:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for(int i = 0; i < edge[r].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i = 0; i < roots.size(); i++) roots[i] = maxdist[roots[i]] * -1;
      |                    ~~^~~~~~~~~~~~~~