Submission #992231

#	Time	Username	Problem	Language	Result	Execution time	Memory
992231		Alfraganus	Race (IOI11_race)	C++17	0 / 100	1 ms	2392 KiB

race

#include "race.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;

#define printmp(a) for(auto x : a) cout << x.first << ' ' << x.second << endl;

vector<vector<array<int, 2>>> graph;
vector<int> subtree_size;
vector<bool> removed, used;

struct Centroid_Decomposition{

  void sub_size(int node, int par){
    subtree_size[node] = 1;
    for(auto &child : graph[node]){
      if(child[0] != par and !removed[child[0]]){
        sub_size(child[0], node);
        subtree_size[node] += subtree_size[child[0]];
      }
    }
  }

  int center(int node, int par, int size){
    for(auto [x, y] : graph[node]){
      if(x != par and !removed[x]){
        if(subtree_size[x] * 2 > size)
          return center(x, node, size);
      }
    }
    return node;
  }

  int find_center(int node){
    sub_size(node, -1);
    return center(node, -1, subtree_size[node]);
  }

  int dfs(int node, int k){
    int center = find_center(node);
    removed[center] = true;
    int ans = 1e9;
    map<int, int> mp;
    mp[0] = 0;
    for(auto y : graph[center]){
      if(!removed[y[0]] and y[1] <= k){
        queue<array<int, 3>> q;
        q.push({y[0], y[1], 1});
        used[y[0]] = 1;
        while(!q.empty()){
          array<int, 3> cur = q.front();
          q.pop();
          if(mp.count(k - cur[1]) == 1)
            ans = min(ans, mp[k - cur[1]] + cur[2]);

          for(auto x : graph[cur[0]]){
            if(!used[x[0]] and !removed[x[0]] and cur[1] + x[1] <= k){
              q.push({x[0], cur[1] + x[1], x[2] + 1});
              used[x[0]] = 1;
            }
          }
        }
        q.push({y[0], y[1], 1});
        used[y[0]] = 0;
        while(!q.empty()){
          array<int, 3> cur = q.front();
          q.pop();

          if(mp.count(cur[1]) == 0)
            mp[cur[1]] = cur[2];
          else
            mp[cur[1]] = min(mp[cur[1]], cur[2]);
          
          for(auto x : graph[cur[0]]){
            if(used[x[0]] and !removed[x[0]] and cur[1] + x[1] <= k){
              q.push({x[0], cur[1] + x[1], x[2] + 1});
              used[x[0]] = 0;
            }
          }
        }
      }
    }
    for(auto y : graph[center])
      if(!removed[y[0]])
        ans = min(ans, dfs(y[0], k));
    return ans;
  }

  int get(int k){
    return dfs(0, k);
  }
};

int best_path(int n, int k, int h[][2], int l[]){
    graph.resize(n);
    subtree_size.resize(n);
    removed.resize(n);
    used.resize(n);
    for(int i = 0; i < n - 1; i++){
        graph[h[i][0]].push_back({h[i][1], l[i]});
        graph[h[i][1]].push_back({h[i][0], l[i]});
    }
    Centroid_Decomposition cd;
    int ans = cd.get(k);
    if(ans == 1e9)
      return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int Centroid_Decomposition::dfs(int, int)':
race.cpp:76:49: warning: array subscript 2 is outside array bounds of 'std::array<int, 2> [1]' [-Warray-bounds]
   76 |               q.push({x[0], cur[1] + x[1], x[2] + 1});
race.cpp:74:20: note: while referencing 'x'
   74 |           for(auto x : graph[cur[0]]){
      |                    ^
race.cpp:58:49: warning: array subscript 2 is outside array bounds of 'std::array<int, 2> [1]' [-Warray-bounds]
   58 |               q.push({x[0], cur[1] + x[1], x[2] + 1});
race.cpp:56:20: note: while referencing 'x'
   56 |           for(auto x : graph[cur[0]]){
      |                    ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57