oj.uz

Submission #170896

# Submission time Handle Problem Language Result Execution time Memory
170896 2019-12-26T16:41:36 Z WLZ Race (IOI11_race) C++14
100 / 100
 1964 ms 62728 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, k, ans = INF;
vector< map<int, int> > g;
vector<int> sz;
map<int, int> len, new_len;

int dfs(int u, int par) {
  sz[u] = 1;
  for (auto& v : g[u]) {
    if (v.first != par) {
      sz[u] += dfs(v.first, u);
    }
  }
  return sz[u];
}

int find_centroid(int u, int par, int n) {
  for (auto& v : g[u]) {
    if (v.first != par && sz[v.first] > n / 2) {
      return find_centroid(v.first, u, n);
    }
  }
  return u;
}

void find_path(int u, int par, int cur_dist, int cur_len) {
  if (cur_dist > k) {
    return;
  }
  if (len.count(k - cur_dist)) {
    ans = min(ans, len[k - cur_dist] + cur_len);
  }
  if (!new_len.count(cur_dist)) {
    new_len[cur_dist] = cur_len;
  } else {
    new_len[cur_dist] = min(new_len[cur_dist], cur_len);
  }
  for (auto& v : g[u]) {
    if (v.first != par) {
      find_path(v.first, u, cur_dist + v.second, cur_len + 1);
    }
  }
}

void find_path(int u, int par) {
  len.clear();
  new_len.clear();
  len[0] = 0;
  for (auto& v : g[u]) {
    if (v.first != par) {
      find_path(v.first, u, v.second, 1);
      for (auto& p : new_len) {
        if (!len.count(p.first)) {
          len[p.first] = p.second;
        } else {
          len[p.first] = min(len[p.first], p.second);
        }
      }
      new_len.clear();
    }
  }
}

void decompose(int u, int par) {
  int n = dfs(u, par);
  int centroid = find_centroid(u, par, n);
  find_path(centroid, par);
  vector<int> tmp;
  for (auto& v : g[centroid]) {
    tmp.push_back(v.first);
  }
  for (auto& v : tmp) {
    if (v != par) {
      g[centroid].erase(v);
      g[v].erase(centroid);
      decompose(v, centroid);
    }
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N, k = K;
  g.resize(n);
  sz.resize(n);
  for (int i = 0; i < n - 1; i++) {
    g[H[i][0]].insert({H[i][1], L[i]});
    g[H[i][1]].insert({H[i][0], L[i]});
  }
  decompose(0, -1);
  if (ans == INF) {
    return -1;
  }
  return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 4 ms 504 KB Output is correct
22 Correct 3 ms 504 KB Output is correct
23 Correct 3 ms 504 KB Output is correct
24 Correct 3 ms 504 KB Output is correct
25 Correct 5 ms 504 KB Output is correct
26 Correct 4 ms 504 KB Output is correct
27 Correct 3 ms 504 KB Output is correct
28 Correct 5 ms 508 KB Output is correct
29 Correct 5 ms 504 KB Output is correct
30 Correct 5 ms 632 KB Output is correct
31 Correct 5 ms 632 KB Output is correct
32 Correct 5 ms 632 KB Output is correct
33 Correct 5 ms 632 KB Output is correct
34 Correct 4 ms 504 KB Output is correct
35 Correct 4 ms 504 KB Output is correct
36 Correct 4 ms 508 KB Output is correct
37 Correct 5 ms 504 KB Output is correct
38 Correct 5 ms 504 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 517 ms 17348 KB Output is correct
20 Correct 419 ms 17504 KB Output is correct
21 Correct 463 ms 17400 KB Output is correct
22 Correct 417 ms 17452 KB Output is correct
23 Correct 200 ms 17400 KB Output is correct
24 Correct 193 ms 17660 KB Output is correct
25 Correct 315 ms 21496 KB Output is correct
26 Correct 193 ms 25208 KB Output is correct
27 Correct 477 ms 34612 KB Output is correct
28 Correct 584 ms 50296 KB Output is correct
29 Correct 607 ms 49272 KB Output is correct
30 Correct 557 ms 34552 KB Output is correct
31 Correct 466 ms 34456 KB Output is correct
32 Correct 527 ms 34680 KB Output is correct
33 Correct 753 ms 34808 KB Output is correct
34 Correct 438 ms 35404 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 4 ms 504 KB Output is correct
22 Correct 3 ms 504 KB Output is correct
23 Correct 3 ms 504 KB Output is correct
24 Correct 3 ms 504 KB Output is correct
25 Correct 5 ms 504 KB Output is correct
26 Correct 4 ms 504 KB Output is correct
27 Correct 3 ms 504 KB Output is correct
28 Correct 5 ms 508 KB Output is correct
29 Correct 5 ms 504 KB Output is correct
30 Correct 5 ms 632 KB Output is correct
31 Correct 5 ms 632 KB Output is correct
32 Correct 5 ms 632 KB Output is correct
33 Correct 5 ms 632 KB Output is correct
34 Correct 4 ms 504 KB Output is correct
35 Correct 4 ms 504 KB Output is correct
36 Correct 4 ms 508 KB Output is correct
37 Correct 5 ms 504 KB Output is correct
38 Correct 5 ms 504 KB Output is correct
39 Correct 517 ms 17348 KB Output is correct
40 Correct 419 ms 17504 KB Output is correct
41 Correct 463 ms 17400 KB Output is correct
42 Correct 417 ms 17452 KB Output is correct
43 Correct 200 ms 17400 KB Output is correct
44 Correct 193 ms 17660 KB Output is correct
45 Correct 315 ms 21496 KB Output is correct
46 Correct 193 ms 25208 KB Output is correct
47 Correct 477 ms 34612 KB Output is correct
48 Correct 584 ms 50296 KB Output is correct
49 Correct 607 ms 49272 KB Output is correct
50 Correct 557 ms 34552 KB Output is correct
51 Correct 466 ms 34456 KB Output is correct
52 Correct 527 ms 34680 KB Output is correct
53 Correct 753 ms 34808 KB Output is correct
54 Correct 438 ms 35404 KB Output is correct
55 Correct 38 ms 2168 KB Output is correct
56 Correct 27 ms 2040 KB Output is correct
57 Correct 240 ms 17552 KB Output is correct
58 Correct 135 ms 17780 KB Output is correct
59 Correct 629 ms 31136 KB Output is correct
60 Correct 1964 ms 62728 KB Output is correct
61 Correct 607 ms 34836 KB Output is correct
62 Correct 666 ms 34780 KB Output is correct
63 Correct 856 ms 34828 KB Output is correct
64 Correct 1838 ms 41840 KB Output is correct
65 Correct 468 ms 35704 KB Output is correct
66 Correct 1259 ms 47128 KB Output is correct
67 Correct 544 ms 36212 KB Output is correct
68 Correct 949 ms 38392 KB Output is correct
69 Correct 932 ms 38620 KB Output is correct
70 Correct 848 ms 36732 KB Output is correct