Submission #272942

#	Time	Username	Problem	Language	Result	Execution time	Memory
272942		hhh07	Race (IOI11_race)	C++14	31 / 100	432 ms	35452 KiB

race

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cstring>
#include <climits>
#include <algorithm>

using namespace std;

typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;

int K, N, res, curr_maks, curr_node, cnt, ans;
vector<vii> adjList(200001);
vi subtree, gotov, mini, moze;

void cal_subtree(int curr, int prev){
    int D = 0;
    for (int i = 0; i < adjList[curr].size(); i++){
        int t = adjList[curr][i].first;
        
        if (t != prev && !gotov[t]){
            cal_subtree(t, curr);
            D += 1 + subtree[t];
        }
    }
    subtree[curr] = D;
}

void find_centr(int curr, int prev, int uk){
  int x = uk - subtree[curr] - 1;
  for (int i = 0; i < adjList[curr].size(); i++){
    int t = adjList[curr][i].first;
      if (t != prev && !gotov[t]){
      find_centr(t, curr, uk);
      x = max(x, 1 + subtree[t]);
    }
  }

  if (curr_maks > x){
    curr_node = curr;
    curr_maks = x;
  }
}

void dfs1(int curr, int prev, int dist, int depth){
  if (dist > K)
    return;
  
  if (moze[dist] != cnt || depth < mini[dist]){
    moze[dist] = cnt;
    mini[dist] = depth;
  }

  for (int i = 0; i < adjList[curr].size(); i++){
    int t = adjList[curr][i].first;
    if (t != prev && !gotov[t])
      dfs1(t, curr, dist + adjList[curr][i].second, depth + 1);
  }
}



void dfs2(int curr, int prev, int dist, int depth){
  if (dist > K)
    return;
    //cout << curr << " " << prev << " " << dist << endl;
    if (moze[K - dist] == cnt){
        ans = min(ans, depth + mini[K - dist]);
        //cout << curr << " " << prev << " " << dist << endl;
    }
    if (K == dist){
        ans = min(ans, depth);
        //cout << curr << " " << prev << " " << dist << endl;
    }
    
  for (int i = 0; i < adjList[curr].size(); i++){
    int t = adjList[curr][i].first;
    if (t != prev && !gotov[t])
      dfs2(t, curr, dist + adjList[curr][i].second, depth + 1);
  }
}

void solve(int curr){

  cal_subtree(curr, -1);
  if (subtree[curr] <= 1)
    return;
  curr_node = -1; curr_maks = INT_MAX;
  find_centr(curr, -1, subtree[curr] + 1);
  int centr = curr_node;
    //cout << centr << endl;
    cnt++;
  for (int i = 0; i < adjList[centr].size(); i++){
    int t = adjList[centr][i].first;
    if (!gotov[t]){
      dfs2(t, centr, adjList[centr][i].second, 1);
      dfs1(t, centr, adjList[centr][i].second, 1);
    }
  }
  //1. i 2. dfs

  gotov[centr] = true;
  
  
  for (int i = 0; i < adjList[centr].size(); i++){
    int t = adjList[centr][i].first;
    if (!gotov[t])
      solve(t);
  }
}

int best_path(int n, int k, int h[][2], int l[]){
    res = INT_MAX;
    N = n; K = k;
    for (int i = 0; i < n - 1; i++){
        adjList[h[i][0]].push_back({h[i][1], l[i]});
        adjList[h[i][1]].push_back({h[i][0], l[i]});
    }
    gotov.assign(n, false);
    mini.assign(n, 0);
    subtree.assign(n, 0);
    moze.assign(n, -1);
    cnt = 0;
    ans = INT_MAX;
    solve(0);
    if (ans == INT_MAX)
        return -1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void cal_subtree(int, int)':
race.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < adjList[curr].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void find_centr(int, int, int)':
race.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i = 0; i < adjList[curr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs1(int, int, int, int)':
race.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for (int i = 0; i < adjList[curr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs2(int, int, int, int)':
race.cpp:68:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |   if (dist > K)
      |   ^~
race.cpp:71:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   71 |     if (moze[K - dist] == cnt){
      |     ^~
race.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i = 0; i < adjList[curr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for (int i = 0; i < adjList[centr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~
race.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (int i = 0; i < adjList[centr].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~

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