oj.uz

답안 #335198

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335198 2020-12-11T12:24:54 Z blue 꿈 (IOI13_dreaming) C++17
0 / 100
 85 ms 14188 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> maxdist(100001, 0);
vector<int> children(100001, 0);
vector<int> visit(100001, 0);
vector<int> roots;

struct distcomp
{
    bool operator () (int a, int b)
    {
        if(maxdist[a] == maxdist[b]) return a < b;
        return maxdist[a] < maxdist[b];
    }
};

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]-A[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<int> tbv;
    for(int i = 0; i < N; i++)
    {
        if(edge[i].size() == 0) roots.push_back(0);
        if(edge[i].size() == 1) tbv.insert(i);
    }

    int u, v, w;
    while(!tbv.empty())
    {
        u = *tbv.begin();
        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])
            {
                children[v]++;
                maxdist[v] = max(maxdist[v], maxdist[u] + w);
                if(children[v] == edge[v].size() - 1) tbv.insert(v);
            }
            else
            {
                maxdist[u] = max(maxdist[u], maxdist[v] + w);
            }
        }
        if(edge[u].size() == children[u]) roots.push_back(maxdist[u]);
    }
    if(M == N-1) return roots[0];
    else
    {
        sort(roots.begin(), roots.end());
        return roots[roots.size() - 2] + L + roots[roots.size() - 1];
    }
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i = 0; i < edge[u].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:60: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]
   60 |                 if(children[v] == edge[v].size() - 1) tbv.insert(v);
dreaming.cpp:67:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   67 |         if(edge[u].size() == children[u]) roots.push_back(maxdist[u]);

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 14188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 14188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 14188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 13932 KB Output is correct
2 Incorrect 63 ms 14060 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 14188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 85 ms 14188 KB Output isn't correct
2 Halted 0 ms 0 KB -