oj.uz

Submission #336013

# Submission time Handle Problem Language Result Execution time Memory
336013 2020-12-14T13:29:44 Z blue Dreaming (IOI13_dreaming) C++11
0 / 100
 70 ms 13676 KB 
#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]]++;
    }

    set<distcomp> tbv, tbv2;


        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;


    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: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;
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 13036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 13036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 13036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 13676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 13036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 13036 KB Output isn't correct
2 Halted 0 ms 0 KB -