oj.uz

Submission #96186

# Submission time Handle Problem Language Result Execution time Memory
96186 2019-02-06T19:16:26 Z SecretAgent007 Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 13176 KB 
#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){
    if(diste[node] == diam/2){
        radius = diam/2;
        return;
    }
    if(diste[node] < diam/2){
        radius = min(max(diste[last], diam-diste[last]), max(diste[node], diam-diste[node]));
        return ;
    }
    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;
    for(int i = 0; i < 100009; i++){
        diste[i] = -1;
    }
    Radius(A, -1,0);
    radius = 0;
    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
        }
    }
    sort(ans.begin(), ans.begin()+t);
    reverse(ans.begin(), ans.begin()+t);
    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;
}
/*
int 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
*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13176 KB Output is correct
2 Correct 68 ms 13176 KB Output is correct
3 Correct 44 ms 9720 KB Output is correct
4 Correct 13 ms 4864 KB Output is correct
5 Correct 11 ms 4224 KB Output is correct
6 Correct 18 ms 5632 KB Output is correct
7 Incorrect 5 ms 3584 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13176 KB Output is correct
2 Correct 68 ms 13176 KB Output is correct
3 Correct 44 ms 9720 KB Output is correct
4 Correct 13 ms 4864 KB Output is correct
5 Correct 11 ms 4224 KB Output is correct
6 Correct 18 ms 5632 KB Output is correct
7 Incorrect 5 ms 3584 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13176 KB Output is correct
2 Correct 68 ms 13176 KB Output is correct
3 Correct 44 ms 9720 KB Output is correct
4 Correct 13 ms 4864 KB Output is correct
5 Correct 11 ms 4224 KB Output is correct
6 Correct 18 ms 5632 KB Output is correct
7 Incorrect 5 ms 3584 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 5760 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13176 KB Output is correct
2 Correct 68 ms 13176 KB Output is correct
3 Correct 44 ms 9720 KB Output is correct
4 Correct 13 ms 4864 KB Output is correct
5 Correct 11 ms 4224 KB Output is correct
6 Correct 18 ms 5632 KB Output is correct
7 Incorrect 5 ms 3584 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13176 KB Output is correct
2 Correct 68 ms 13176 KB Output is correct
3 Correct 44 ms 9720 KB Output is correct
4 Correct 13 ms 4864 KB Output is correct
5 Correct 11 ms 4224 KB Output is correct
6 Correct 18 ms 5632 KB Output is correct
7 Incorrect 5 ms 3584 KB Output isn't correct
8 Halted 0 ms 0 KB -