Submission #195619

#	Time	Username	Problem	Language	Result	Execution time	Memory
195619		jovan_b	Dreaming (IOI13_dreaming)	C++17	100 / 100	264 ms	15096 KiB

dreaming

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

using namespace std;

typedef long long ll;

int n, m, l;
int far1, far2;
int cnt;
int in[100005];
int out[100005];
int parent[100005];
int dispar[100005];
int maxdist = 0;
bool visited1[100005];
bool visited2[100005];
vector <pair <int, int>> graf[100005];
vector <pair <int, int>> vec;

bool is_parent(int a, int b){
    return in[a] <= in[b] && out[b] <= out[a];
}

void dfs1(int v, int dist){
    if(dist > maxdist){
        far1 = v;
        maxdist = dist;
    }
    in[v] = ++cnt;
    visited1[v] = 1;
    for(auto par : graf[v]){
        int c = par.first;
        if(visited1[c]) continue;
        parent[c] = v;
        dispar[c] = par.second;
        dfs1(c, dist + par.second);
    }
    out[v] = ++cnt;
}

void dfs2(int v, int dist){
    if(dist > maxdist){
        far2 = v;
        maxdist = dist;
    }
    visited2[v] = 1;
    for(auto par : graf[v]){
        int c = par.first;
        if(visited2[c]) continue;
        dfs2(c, dist + par.second);
    }
}

void uradi(int i){
    far1 = i;
    maxdist = 0;
    dfs1(i, 0);
    maxdist = 0;
    far2 = far1;
    dfs2(far1, 0);
    int minres = maxdist;
    int koji = far1;
    int x = far2;
    int trendist = 0;
    while(!is_parent(x, far1)){
        trendist += dispar[x];
        x = parent[x];
        if(max(trendist, maxdist - trendist) < minres){
            minres = max(trendist, maxdist - trendist);
            koji = x;
        }
    }
    x = far1;
    trendist = 0;
    while(!is_parent(x, far2)){
        trendist += dispar[x];
        x = parent[x];
        if(max(trendist, maxdist - trendist) < minres){
            minres = max(trendist, maxdist - trendist);
            koji = x;
        }
    }
    vec.push_back({minres, koji});
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    n = N;
    m = M;
    l = L;
    for(int i=0; i<n; i++){
        graf[A[i]+1].push_back({B[i]+1, T[i]});
        graf[B[i]+1].push_back({A[i]+1, T[i]});
    }
    for(int i=1; i<=n; i++){
        if(!visited1[i]) uradi(i);
    }
    sort(vec.begin(), vec.end());
    reverse(vec.begin(), vec.end());
    for(int i=1; i<vec.size(); i++){
        graf[vec[0].second].push_back({vec[i].second, l});
        graf[vec[i].second].push_back({vec[0].second, l});
    }
    for(int i=1; i<=n; i++){
        visited1[i] = visited2[i] = 0;
    }
    maxdist = 0;
    far1 = 1;
    dfs1(1, 0);
    maxdist = 0;
    far2 = far1;
    dfs2(far1, 0);
    return maxdist;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:101:19: 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