Submission #66384

#	Time	Username	Problem	Language	Result	Execution time	Memory
66384		zubec	Dreaming (IOI13_dreaming)	C++14	100 / 100	187 ms	24320 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100100;

vector <pair<int, int> > g[N];
vector <int> pref[N];

bool used[N];

int dp[N][2], n;

void dfs1(int v, int p){
    used[v] = 1;
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, len = g[v][i].second;
        if (to == p)
            continue;
        dfs1(to, v);
        dp[v][0] = max(dp[v][0], dp[to][0] + len);
    }
}

int mn, pos = 0;

void dfs2(int v, int p){
    int mx = 0;
    for (int i = g[v].size()-1; i >= 0; i--){
        int to = g[v][i].first, len = g[v][i].second;
        if (to == p)
            continue;
        mx = max(mx, dp[to][0]+len);
        pref[v].push_back(mx);
    }
    mx = max(mx, dp[p][1]);
    if (mx < mn){
        mn = mx;
        pos = v;
    }
    mx = dp[p][1];
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, len = g[v][i].second;
        if (to == p)
            continue;
        pref[v].pop_back();
        int mx2 = 0;
        if (!pref[v].empty())
            mx2 = pref[v].back();
        dp[v][1] = max(mx, mx2)+len;
        dfs2(to, v);
        mx = max(mx, dp[to][0]+len);
    }
}

void dfs3(int v, int p, ll curLen){
    if (curLen > mn){
        mn = curLen;
        pos = v;
    }
    for (int i = 0; i < g[v].size(); i++){
        int to = g[v][i].first, len = g[v][i].second;
        if (to == p)
            continue;
        dfs3(to, v, curLen+len);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    n = N;
    for (int i = 1; i <= M; i++){
        int u = A[i-1]+1, v = B[i-1]+1, c = T[i-1];
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    vector <pair<int, int> > vec;
    for (int i = 1; i <= n; i++){
        if (used[i])
            continue;

        dfs1(i, 0);
        mn = 1e9+7;
        pos = 0;
        dfs2(i, 0);
        vec.push_back({mn, pos});
    }
    sort(vec.rbegin(), vec.rend());
    int u = vec[0].second;
    for (int i = 1; i < vec.size(); i++){
        int v = vec[i].second;
        g[u].push_back({v, L});
        g[v].push_back({u, L});
    }

    mn = -1;
    dfs3(1, 0, 0);
    mn = -1;
    dfs3(pos, 0, 0);

    return mn;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:17:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs3(int, int, ll)':
dreaming.cpp:62:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:90:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < vec.size(); i++){
                     ~~^~~~~~~~~~~~

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