oj.uz

답안 #335206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335206 2020-12-11T13:25:28 Z blue 꿈 (IOI13_dreaming) C++17
0 / 100
 107 ms 13944 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
{
    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]-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<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());
        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});
            }
        }
        if(edge[u].size() == children[u]) roots.push_back(u);
    }
//    cout << '\n';
//    cout << roots.size() << '\n';
    int res = 0;
    for(int r: roots)
    {
    //    cout << "r = " << r << '\n';
        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';
    if(M == N-1) return res;
    else
    {
        for(int i = 0; i < roots.size(); i++) roots[i] = maxdist[roots[i]];
        sort(roots.begin(), roots.end());
        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;
}

Compilation message

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

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 13036 KB Output is correct
2 Correct 107 ms 12908 KB Output is correct
3 Correct 49 ms 10604 KB Output is correct
4 Correct 13 ms 7148 KB Output is correct
5 Correct 11 ms 6892 KB Output is correct
6 Correct 18 ms 7660 KB Output is correct
7 Incorrect 5 ms 6252 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 13036 KB Output is correct
2 Correct 107 ms 12908 KB Output is correct
3 Correct 49 ms 10604 KB Output is correct
4 Correct 13 ms 7148 KB Output is correct
5 Correct 11 ms 6892 KB Output is correct
6 Correct 18 ms 7660 KB Output is correct
7 Incorrect 5 ms 6252 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 13036 KB Output is correct
2 Correct 107 ms 12908 KB Output is correct
3 Correct 49 ms 10604 KB Output is correct
4 Correct 13 ms 7148 KB Output is correct
5 Correct 11 ms 6892 KB Output is correct
6 Correct 18 ms 7660 KB Output is correct
7 Incorrect 5 ms 6252 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 13036 KB Output is correct
2 Correct 107 ms 12908 KB Output is correct
3 Correct 49 ms 10604 KB Output is correct
4 Correct 13 ms 7148 KB Output is correct
5 Correct 11 ms 6892 KB Output is correct
6 Correct 18 ms 7660 KB Output is correct
7 Incorrect 5 ms 6252 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 13036 KB Output is correct
2 Correct 107 ms 12908 KB Output is correct
3 Correct 49 ms 10604 KB Output is correct
4 Correct 13 ms 7148 KB Output is correct
5 Correct 11 ms 6892 KB Output is correct
6 Correct 18 ms 7660 KB Output is correct
7 Incorrect 5 ms 6252 KB Output isn't correct
8 Halted 0 ms 0 KB -