Submission #96191

#	Time	Username	Problem	Language	Result	Execution time	Memory
96191		SecretAgent007	Dreaming (IOI13_dreaming)	C++17	100 / 100	124 ms	15644 KiB

dreaming

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

vector< pair<int, int> > Graph[100009];
vector< bool > v(100009, false);
vector< int > ans(100009);

int Maxi = 0;
int maxi = -1;

int Last = 0;

void DFS(int node, int last, int dist){
   // cout << node << ' ' << last << endl;
    if(dist > Maxi){
        Maxi = dist;
        Last = node;
    }
    v[node] = true;
    for(auto a : Graph[node]){
        if(a.first != last){
            DFS(a.first, node,dist+a.second);
        }
    }
}

vector<int> diste(100009);

int radius;

void Radius(int node, int last, int dist){
    diste[node] = max(diste[node], dist);
    for(auto a : Graph[node]){
        if(a.first != last){
            Radius(a.first, node, dist+a.second);
        }
    }
}

void R(int node, int last, int dist, int diam){
    radius = min(radius, max(dist, diste[node]));
    for(auto a : Graph[node]){
        if(a.first != last){
            R(a.first, node, dist+a.second, diam);
        }
    }
}

int F(int a){
   // cout << a << endl;
    Maxi = -1;
    DFS(a,-1,0);
    int A = Last;
   // cout << A << endl;
    Maxi = -1;
    DFS(A,-1,0);
    //cout << A << ' ' << "Diameter " << Maxi << endl;
    maxi = max(Maxi, maxi);
    int B = Last;
    int diam = Maxi;
    //cout << "Between node " << A << " and " << B << ' ' << diam << endl;
    Radius(A, -1,0);
    radius = INT_MAX;
    R(B,-1,0,diam);
    //cout << radius << endl;
    return radius;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; i++){
        Graph[A[i]].push_back(make_pair(B[i], T[i]));
        Graph[B[i]].push_back(make_pair(A[i], T[i]));
    }
    int t = 0;
    for(int i = 0; i < N; i++){
        if(!v[i]){
            ans[t++] = F(i);//FUNCTION
        }
    }
    for(int i = 0; i < 100009; i++){
        diste[i] = -1;
    }
    sort(ans.begin(), ans.begin()+t);
    reverse(ans.begin(), ans.begin()+t);
    /*for(int i = 0; i < t; i++){
        cout << ans[i] << ' ';
    }
    cout << endl;*/
    if(t > 1){
        maxi = max(maxi, ans[0]+ans[1]+L);
        if(t > 2){
            maxi = max(maxi, ans[1]+ans[2]+2*L);
        }
    }
    return maxi;
}
/*
signed main(){
    int n, m, l;
    cin >> n >> m >> l;
    int a[m];
    int b[m];
    int t[m];
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> t[i];
    }
    cout << travelTime(n,m,l,a,b,t) << endl;
}*/
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3

4 2 1
0 1 1
2 3 2
*/

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