oj.uz

Submission #1010217

# Submission time Handle Problem Language Result Execution time Memory
1010217 2024-06-28T13:24:40 Z spacewalker Dreaming (IOI13_dreaming) C++17
18 / 100
 32 ms 9420 KB 
#include <bits/stdc++.h>

using namespace std;

#include "dreaming.h"

vector<pair<int, int>> distances(const vector<vector<pair<int, int>>> &graph, int start, vector<int> &dist, vector<int> &par) {
  queue<int> q;
  q.push(start);
  dist[start] = 0;
  vector<pair<int, int>> component;
  while (!q.empty()) {
    int cur = q.front(); q.pop();
    component.emplace_back(dist[cur], cur);
    for (auto [u, w] : graph[cur]) {
      if (dist[u] != -1) continue;
      dist[u] = dist[cur] + w;
      par[u] = cur;
      q.push(u);
    }
  }
  return component;
}

int find_cc_radius(const vector<vector<pair<int, int>>> &graph, int start, vector<int> &dist, vector<int> &par) {
  vector<pair<int, int>> cc = distances(graph, start, dist, par);
  int v1 = max_element(cc.begin(), cc.end())->second;
  // reset the dist array, so we can run the second BFS
  for (auto [_, v] : cc) dist[v] = -1;
  cc = distances(graph, v1, dist, par);
  int v2 = max_element(cc.begin(), cc.end())->second;
  // The "center" of the tree must be on the v1-v2 path.
  int diameter = dist[v2];
  int ans = diameter;
  for (; v2 != v1; v2 = par[v2]) {
    ans = min(ans, max(dist[v2], diameter - dist[v2]));
  }
  return ans;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
  vector<int> radius;
  vector<vector<pair<int, int>>> graph(N);
  for (int i = 0; i < M; ++i) {
    graph[A[i]].emplace_back(B[i], T[i]);
    graph[B[i]].emplace_back(A[i], T[i]);
  }
  vector<int> visited(N, -1), par(N, -1);
  for (int i = 0; i < N; ++i) {
    if (visited[i] != -1) continue;
    radius.emplace_back(find_cc_radius(graph, i, visited, par));
  }
  sort(radius.begin(), radius.end(), greater());
  if (radius.size() == 1) {
    return radius[0];
  } else if (radius.size() == 2) {
    return radius[0] + radius[1] + L;
  } else {
    return max(radius[0] + radius[1] + L, radius[1] + radius[2] + 2 * L);
  }
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5996 KB Output is correct
2 Correct 21 ms 6108 KB Output is correct
3 Correct 21 ms 5980 KB Output is correct
4 Correct 21 ms 6108 KB Output is correct
5 Correct 21 ms 5952 KB Output is correct
6 Correct 21 ms 6624 KB Output is correct
7 Correct 24 ms 6232 KB Output is correct
8 Correct 19 ms 5976 KB Output is correct
9 Correct 27 ms 5832 KB Output is correct
10 Correct 25 ms 6232 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 14 ms 4136 KB Output is correct
13 Correct 13 ms 4056 KB Output is correct
14 Correct 12 ms 4052 KB Output is correct
15 Correct 13 ms 4120 KB Output is correct
16 Correct 13 ms 4056 KB Output is correct
17 Correct 13 ms 4112 KB Output is correct
18 Correct 12 ms 4052 KB Output is correct
19 Correct 13 ms 4128 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 444 KB Output is correct
23 Correct 11 ms 4044 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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