oj.uz

Submission #548611

# Submission time Handle Problem Language Result Execution time Memory
548611 2022-04-14T00:18:15 Z DavidDamian Race (IOI11_race) C++11
100 / 100
 486 ms 93388 KB 
#include "race.h"
#include <vector>
#include <map>
#include <climits>
#include <iostream>
#ifndef maxn
#define maxn 200005

using namespace std;
typedef long long ll;
struct edge {
  int to;
  ll w;
  edge() {

  }
  edge(int t, int w_) {
    to = t;
    w = w_;
  }
};

vector<edge> adjList[maxn];
int subtreeSize[maxn];
map<ll, int>* sack[maxn]; // Holds pairs (distance to root, min edges to root)
// cannot hold (distance to current node, min edges to current node) since these are relative and would have to be updated
int k; // Searched dist
int minimum; // Answer, minimum number of edges
void update(int u, ll dist, int depth) {
  if ((*sack[u]).find(dist) == (*sack[u]).end())
    (*sack[u])[dist] = INT_MAX;

  (*sack[u])[dist] = min((*sack[u])[dist], depth);
}

void printSack(int u) {
  cout << "Sack of " << u << endl;
  for (pair<ll, int> p : *sack[u]) {
    cout << p.first << " " << p.second << endl;
  }
  cout << endl;
}

void search(int u, int p, int greatestChild, int depth, ll dist) {

  for (edge e : adjList[u]) {
    int v = e.to;
    ll w = e.w;
    if (v == p || v == greatestChild) continue;
    for (pair<ll, int> curEndpoint : *sack[v]) {
      ll curDist = curEndpoint.first - dist;
      int curEdges = curEndpoint.second - depth;
      // Search for the complement
      int complement = k - curDist;
      int searchedComplement = complement + dist;
      if ((*sack[u]).find(searchedComplement) != (*sack[u]).end()) {
        // Found two-part path
        int edges = curEdges + (*sack[u])[searchedComplement] - depth;
        minimum = min(minimum, edges);
      }
    }

    // Copy information from this child in order to allow others to find routes to already computed child

    for (pair<ll, int> curEndpoint : *sack[v]) {
      update(u, curEndpoint.first, curEndpoint.second);
    }
  }

  int searchedDist = k + dist;
  if ((*sack[u]).find(searchedDist) != (*sack[u]).end()) { // Found one-part path
    int realEdgesCnt = (*sack[u])[searchedDist] - depth; // Edges relative to this node
    minimum = min(minimum, realEdgesCnt);
  }

}

void dfs(int u, int p, int depth, ll dist) {
  subtreeSize[u] = 1;
  int maxSubtreeSize = 0, greatestChild = -1;
  for (edge e : adjList[u]) {
    int v = e.to;
    ll w = e.w;
    if (v == p) continue;
    dfs(v, u, depth + 1, dist + w);
    subtreeSize[u] += subtreeSize[v];
    if (subtreeSize[v] > maxSubtreeSize) {
      maxSubtreeSize = subtreeSize[v];
      greatestChild = v;
    }
  }
  if (greatestChild == -1) {
    // Leaf node
    sack[u] = new map<ll, int>();
  }
  else {
    sack[u] = sack[greatestChild];
  }
  search(u, p, greatestChild, depth, dist);
  update(u, dist, depth);
}

int best_path(int N, int K, int H[][2], int L[])
{
  k = K;
  minimum = INT_MAX;
  for (int i = 0; i < N - 1; i++) {
    int a = H[i][0] + 1;
    int b = H[i][1] + 1;
    ll w = L[i];
    adjList[a].push_back(edge(b, w));
    adjList[b].push_back(edge(a, w));
  }
  dfs(1, 0, 0, 0);
  return (minimum == INT_MAX? -1 : minimum);
}

#endif

Compilation message

race.cpp: In function 'void search(int, int, int, int, ll)':
race.cpp:48:8: warning: unused variable 'w' [-Wunused-variable]
   48 |     ll w = e.w;
      |        ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5008 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4968 KB Output is correct
9 Correct 3 ms 5008 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 5008 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5008 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4968 KB Output is correct
9 Correct 3 ms 5008 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 5008 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 4 ms 5204 KB Output is correct
22 Correct 4 ms 5332 KB Output is correct
23 Correct 4 ms 5332 KB Output is correct
24 Correct 4 ms 5332 KB Output is correct
25 Correct 4 ms 5332 KB Output is correct
26 Correct 4 ms 5332 KB Output is correct
27 Correct 3 ms 5184 KB Output is correct
28 Correct 4 ms 5332 KB Output is correct
29 Correct 4 ms 5332 KB Output is correct
30 Correct 4 ms 5332 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct
32 Correct 4 ms 5332 KB Output is correct
33 Correct 4 ms 5332 KB Output is correct
34 Correct 4 ms 5204 KB Output is correct
35 Correct 4 ms 5148 KB Output is correct
36 Correct 3 ms 5204 KB Output is correct
37 Correct 3 ms 5140 KB Output is correct
38 Correct 3 ms 5204 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5008 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4968 KB Output is correct
9 Correct 3 ms 5008 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 5008 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 105 ms 27464 KB Output is correct
20 Correct 104 ms 27428 KB Output is correct
21 Correct 108 ms 27732 KB Output is correct
22 Correct 106 ms 28168 KB Output is correct
23 Correct 151 ms 41808 KB Output is correct
24 Correct 113 ms 36044 KB Output is correct
25 Correct 80 ms 18932 KB Output is correct
26 Correct 45 ms 22760 KB Output is correct
27 Correct 182 ms 42284 KB Output is correct
28 Correct 246 ms 53400 KB Output is correct
29 Correct 268 ms 52972 KB Output is correct
30 Correct 179 ms 42240 KB Output is correct
31 Correct 183 ms 42256 KB Output is correct
32 Correct 216 ms 42464 KB Output is correct
33 Correct 189 ms 34820 KB Output is correct
34 Correct 343 ms 67580 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5008 KB Output is correct
2 Correct 3 ms 5004 KB Output is correct
3 Correct 3 ms 5012 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 5004 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4968 KB Output is correct
9 Correct 3 ms 5008 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 4 ms 5008 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 4 ms 5204 KB Output is correct
22 Correct 4 ms 5332 KB Output is correct
23 Correct 4 ms 5332 KB Output is correct
24 Correct 4 ms 5332 KB Output is correct
25 Correct 4 ms 5332 KB Output is correct
26 Correct 4 ms 5332 KB Output is correct
27 Correct 3 ms 5184 KB Output is correct
28 Correct 4 ms 5332 KB Output is correct
29 Correct 4 ms 5332 KB Output is correct
30 Correct 4 ms 5332 KB Output is correct
31 Correct 4 ms 5332 KB Output is correct
32 Correct 4 ms 5332 KB Output is correct
33 Correct 4 ms 5332 KB Output is correct
34 Correct 4 ms 5204 KB Output is correct
35 Correct 4 ms 5148 KB Output is correct
36 Correct 3 ms 5204 KB Output is correct
37 Correct 3 ms 5140 KB Output is correct
38 Correct 3 ms 5204 KB Output is correct
39 Correct 105 ms 27464 KB Output is correct
40 Correct 104 ms 27428 KB Output is correct
41 Correct 108 ms 27732 KB Output is correct
42 Correct 106 ms 28168 KB Output is correct
43 Correct 151 ms 41808 KB Output is correct
44 Correct 113 ms 36044 KB Output is correct
45 Correct 80 ms 18932 KB Output is correct
46 Correct 45 ms 22760 KB Output is correct
47 Correct 182 ms 42284 KB Output is correct
48 Correct 246 ms 53400 KB Output is correct
49 Correct 268 ms 52972 KB Output is correct
50 Correct 179 ms 42240 KB Output is correct
51 Correct 183 ms 42256 KB Output is correct
52 Correct 216 ms 42464 KB Output is correct
53 Correct 189 ms 34820 KB Output is correct
54 Correct 343 ms 67580 KB Output is correct
55 Correct 17 ms 8336 KB Output is correct
56 Correct 9 ms 6868 KB Output is correct
57 Correct 64 ms 26892 KB Output is correct
58 Correct 53 ms 25588 KB Output is correct
59 Correct 95 ms 28972 KB Output is correct
60 Correct 248 ms 52876 KB Output is correct
61 Correct 217 ms 45808 KB Output is correct
62 Correct 179 ms 42300 KB Output is correct
63 Correct 213 ms 42488 KB Output is correct
64 Correct 469 ms 91668 KB Output is correct
65 Correct 486 ms 93388 KB Output is correct
66 Correct 280 ms 52104 KB Output is correct
67 Correct 157 ms 47332 KB Output is correct
68 Correct 331 ms 62604 KB Output is correct
69 Correct 322 ms 63080 KB Output is correct
70 Correct 306 ms 59892 KB Output is correct