oj.uz

Submission #341945

# Submission time Handle Problem Language Result Execution time Memory
341945 2020-12-31T17:51:13 Z ijxjdjd Dreaming (IOI13_dreaming) C++14
0 / 100
 55 ms 15084 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;
const int MAXN = (int)(1e5)+5;
vector<pair<int, int>> adj[MAXN];
int cur = -1;
int curI = -1;
pair<int, int> best;
bool visited[MAXN];
pair<int, int> sep = {(int)(1e9), (int)(1e9)};
int mx = 0;
void furthest(int n, int p, int d) {
    visited[n] = true;
    if (d > cur) {
        cur = d;
        curI = n;
    }
    for (pair<int, int> e : adj[n]) {
        if (e.first != p) {
            furthest(e.first, n, d+e.second);
        }
    }
}
int getBest(int n, int p, int d) {
    if (n == curI) {
        return 0;
    }
    int distTo = (int)(1e9);
    for (pair<int, int> e : adj[n]) {
        if (e.first != p) {
            distTo = min(distTo, getBest(e.first, n, d+e.second) + e.second);
        }
    }
    if (max(d, distTo) < best.first) {
        best = {max(d, distTo), min(d, distTo)};
    }
    return distTo;
}
void getSplit(int n) {
    cur = -1;
    furthest(n, n, 0);
    cur = -1;
    int d1 = curI;
    furthest(d1, d1, 0);
    best = {(int)(1e9), (int)(1e9)};
    getBest(d1, d1, 0);
    if (n == 0) {
        sep=best;
    }
    else if (best.first < (int)(1e9)){
        if (best.first > sep.first) {
            sep.second = sep.first;
            sep.first = best.first;
        }
        else if (best.first > sep.second) {
            sep.second = best.first;
        }
        mx = max(mx, best.first + best.second);

    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++) {
        adj[A[i]].push_back({B[i], T[i]});
        adj[B[i]].push_back({A[i], T[i]});
    }
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            getSplit(i);
        }
    }
    return max(sep.first + sep.second + L, mx);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 15084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 15084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 15084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5484 KB Output is correct
2 Incorrect 21 ms 5484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 15084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 15084 KB Output isn't correct
2 Halted 0 ms 0 KB -