Submission #420492

#	Time	Username	Problem	Language	Result	Execution time	Memory
420492		dxz05	꿈 (IOI13_dreaming)	C++14	65 / 100	171 ms	17296 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 3e2;

vector<pair<int, int>> g[MAXN];

int d[MAXN];
vector<int> comp;
bool visited[MAXN];

void dfs(int v, int p, int dist){
    visited[v] = true;
    d[v] = dist;
    comp.push_back(v);
    for (auto edge : g[v]){
        int u = edge.first, w = edge.second;
        if (u != p) dfs(u, v, dist + w);
    }
}

int dA[MAXN], dB[MAXN];

pair<int, int> get_diameter(int v){
    comp.clear();
    dfs(v, -1, 0);

    int A = v;
    for (int x : comp){
        if (d[x] > d[A]) A = x;
    }

    comp.clear();
    dfs(A, -1, 0);

    int B = v;
    for (int x : comp){
        if (d[x] > d[B]) B = x;
        dA[x] = d[x];
    }

    comp.clear();
    dfs(B, -1, 0);

    for (int x : comp){
        dB[x] = d[x];
        if (max(dA[x], dB[x]) < max(dA[v], dB[v])) v = x;
    }

    return make_pair(dA[B], v);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++){
        g[A[i]].emplace_back(B[i], T[i]);
        g[B[i]].emplace_back(A[i], T[i]);
    }

    vector<pair<int, int>> diameters;

    for (int i = 0; i < N; i++){
        if (!visited[i]){
            diameters.push_back(get_diameter(i));
        }
    }

    sort(diameters.begin(), diameters.end());

    for (int i = 0; i < diameters.size() - 1; i++){
        int x = diameters[i].second, y = diameters.back().second;
        g[x].emplace_back(y, L);
        g[y].emplace_back(x, L);
    }

    return get_diameter(0).first;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < diameters.size() - 1; i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23