Submission #480067

#	Time	Username	Problem	Language	Result	Execution time	Memory
480067		LeMur	Race (IOI11_race)	C++14	0 / 100	5 ms	4940 KiB

race

///////////////////////////////    _LeMur_
#define _CRT_SECURE_NO_WARNINGS
#include "race.h"
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <random>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>

using namespace std;

const int N = 200005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());

vector < pair<int, int> > g[N];
int answ = -1;

bool used[N];
int sz[N];
int nn = 0;
int k;

void dfs_sz(int v, int p) {
  nn++;
  sz[v] = 1;
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    if (to == p) continue;
    if (used[to]) continue;
    dfs_sz(to, v);
    sz[v] += sz[to];
  }
}

int find_center(int v, int p) {
  int mx_sz = -1, gag;
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    if (to == p) continue;
    if (used[to]) continue;
    if (sz[to] > mx_sz) {
      mx_sz = sz[to];
      gag = to;
    }
  }

  if (mx_sz * 2 <= nn) return v;
  return find_center(gag, v);
}

int find_centroid(int v) {
  nn = 0;
  dfs_sz(v, -1);
  int center = find_center(v, -1);
  dfs_sz(center, -1);
  return center;
}

vector < pair<int, int> > mas;
map <int, int> mp;

void update(int &answ, int x) {
  if (answ == -1 || x < answ) {
    answ = x;
  }
}

void solve(int v, int p, int L, int r) {
  if (p != -1) {
    mas.push_back(make_pair(L, r));
  }
  for (int i = 0; i < (int)g[v].size(); i++) {
    int to = g[v][i].first;
    int len = g[v][i].second;
    if (to == p || used[to]) continue;
    solve(to, v, L + len, r + 1);

    if (p == -1) {
      for (int j = 0; j < (int)mas.size(); j++) {
        int L = mas[j].first;
        int d = mas[j].second;
        if (L > k) continue;
        if (L == k) {
          update(answ, d);
        } else {
          if (mp.find(k - L) != mp.end()) {
            update(answ, d + mp[k - L]);
          }
        }
      }

      for (int j = 0; j < (int)mas.size(); j++) {
        int L = mas[j].first;
        int d = mas[j].second;
        if (L > k) continue;
        if (mp.find(L) != mp.end()) {
          mp[L] = min(mp[L], d);
        } else {
          mp[L] = d;
        }
      }
    }
  }
}

void centroid_decomposition() {
  queue <int> q;
  q.push(1);

  while (!q.empty()) {
    int v = q.front();
    q.pop();
    
    int center = find_centroid(v);
    mp.clear();
    solve(center, -1, 0, 0);

    used[center] = true;
    for (int i = 0; i < (int)g[center].size(); i++) {
      int to = g[center][i].first;
      if (used[to]) continue;
      if (sz[to] == 1) continue;
      q.push(to);
    }
  }
}

int best_path(int n, int K, int h[][2], int l[]) {
  k = K;
  for (int i = 0; i < n - 1; i++) {
    int a = h[i][0];
    int b = h[i][1];
    int c = l[i];
    g[a].push_back(make_pair(b, c));
    g[b].push_back(make_pair(a, c));
  }

  centroid_decomposition();

  return answ;
}

// int main() {
//   best_path(11, 12, )
//   return 0;
// }

Compilation message (stderr)

race.cpp: In function 'int find_center(int, int)':
race.cpp:55:5: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |     if (to == p) continue;
      |     ^~

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