Submission #2095678


Source Code Expand

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

vector<PII> g[100010];
map<PII, int> mp;
signed main(void)
{
  int n, d;
  cin >> n >> d;
  REP(i, n-1) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    g[a].PB({b, c});
    g[b].PB({a, c});
    mp[{a, b}] = 1;
  }

  VI dist(n), edge(n);
  function<int(int,int)> dfs1 = [&](int v, int p) -> int {
    if(p != -1 && g[v].size() == 1) return 0;
    for(PII &i: g[v]) if(i.first != p) {
      edge[v] += (mp.find(make_pair(v, i.first)) != mp.end()) + dfs1(i.first, v);
      chmax(dist[v], dist[i.first] + i.second);
    }
    return edge[v];
  };

  dfs1(0, -1);
  // cout << dist << endl << edge << endl;

  // 頂点iから最も遠い頂点までの距離
  VI len(n);
  function<void(int,int,int)> dfs2 = [&](int v, int d_par, int p) {
    vector<PII> d_child;
    d_child.emplace_back(0, -1);
    for(PII &e : g[v]) {
      if(e.first == p) d_child.emplace_back(d_par + e.second, e.first);
      else d_child.emplace_back(dist[e.first] + e.second, e.first);
    }
    sort(d_child.rbegin(), d_child.rend());
    len[v] = d_child[0].first;
    for(PII &e : g[v]) {
      if(e.first == p) continue;
      dfs2(e.first, d_child[d_child[0].second == e.first].first, v);
    }
  };

  vector<bool> able(n, false);
  bool flag = false;
  REP(i, n) if(len[i] <= d) flag = true, able[i] = true;
  if(!flag) {
    cout << -1 << endl;
    return 0;
  }

  // 頂点iに向かうのに辺を反転しないといけない本数
  VI ans(n);
  function<void(int,int,int)> dfs3 = [&](int v, int d_par, int p) {
    // cout << v << " " << d_par << " " << p << endl;
    VI d_child(n);
    for(PII &e : g[v]) {
      int tmp = (mp.find(make_pair(v, e.first)) != mp.end());
      if(e.first == p) {
        ans[v] += d_par + tmp;
        d_child[e.first] = d_par + tmp;
      } else {
        ans[v] += edge[e.first] + tmp;
        d_child[e.first] = edge[e.first] + tmp;
      }
      // cout << e << " " << ans[v] << endl;
    }
    for(PII &e : g[v]) {
      if(e.first == p) continue;
      // ans[v] から e.firstの部分木方向のを引いたやつ
      dfs3(e.first, ans[v] - d_child[e.first], v);
    }
  };

  dfs3(0, 0, -1);
  // cout << ans << endl;

  int ret = INF;
  REP(i, n) {
    if(able[i]) chmin(ret, ans[i]);
  }
  cout << ret << endl;

  return 0;
}

Submission Info

Submission Time
Task E - 限界集落
User ferin_tech
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3462 Byte
Status RE
Exec Time 2491 ms
Memory 33340 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 1
AC × 5
WA × 2
TLE × 25
RE × 13
Set Name Test Cases
Sample 00_sample_00
All 00_sample_00, 01_random_00, 01_random_01, 01_random_02, 01_random_03, 01_random_04, 01_random_05, 01_random_06, 01_random_07, 01_random_08, 01_random_09, 02_path_00, 02_path_01, 02_path_02, 02_path_03, 02_path_04, 02_path_05, 02_path_06, 02_path_07, 02_path_08, 02_path_09, 02_path_10, 02_path_11, 02_path_12, 02_path_13, 02_path_14, 03_uni_00, 03_uni_01, 03_uni_02, 03_uni_03, 03_uni_04, 03_uni_05, 03_uni_06, 03_uni_07, 03_uni_08, 03_uni_09, 03_uni_10, 03_uni_11, 03_uni_12, 03_uni_13, 03_uni_14, hand_00, hand_01, hand_02, hand_03
Case Name Status Exec Time Memory
00_sample_00 AC 2 ms 2560 KB
01_random_00 AC 1370 ms 12104 KB
01_random_01 TLE 2104 ms 17784 KB
01_random_02 TLE 2105 ms 33340 KB
01_random_03 TLE 2104 ms 17424 KB
01_random_04 TLE 2104 ms 23288 KB
01_random_05 TLE 2104 ms 22092 KB
01_random_06 AC 22 ms 3828 KB
01_random_07 TLE 2105 ms 29780 KB
01_random_08 TLE 2104 ms 20288 KB
01_random_09 TLE 2105 ms 29828 KB
02_path_00 TLE 2491 ms -854304 KB
02_path_01 RE 2002 ms -854564 KB
02_path_02 RE 1991 ms -854312 KB
02_path_03 TLE 2431 ms -854300 KB
02_path_04 RE 1820 ms -854160 KB
02_path_05 RE 1815 ms -854204 KB
02_path_06 RE 1753 ms -854188 KB
02_path_07 RE 1928 ms -854076 KB
02_path_08 RE 2005 ms -854308 KB
02_path_09 RE 1733 ms -854308 KB
02_path_10 RE 1825 ms -854308 KB
02_path_11 RE 1832 ms -854328 KB
02_path_12 RE 1928 ms -854304 KB
02_path_13 RE 1922 ms -854300 KB
02_path_14 RE 1821 ms -854200 KB
03_uni_00 TLE 2105 ms 18928 KB
03_uni_01 TLE 2105 ms 19056 KB
03_uni_02 TLE 2105 ms 19056 KB
03_uni_03 TLE 2105 ms 19056 KB
03_uni_04 TLE 2105 ms 19056 KB
03_uni_05 TLE 2105 ms 19056 KB
03_uni_06 TLE 2105 ms 19056 KB
03_uni_07 TLE 2105 ms 19056 KB
03_uni_08 TLE 2105 ms 19056 KB
03_uni_09 TLE 2105 ms 19056 KB
03_uni_10 TLE 2105 ms 19056 KB
03_uni_11 TLE 2105 ms 19056 KB
03_uni_12 TLE 2105 ms 19056 KB
03_uni_13 TLE 2105 ms 19056 KB
03_uni_14 TLE 2105 ms 19056 KB
hand_00 WA 4 ms 2688 KB
hand_01 AC 2 ms 2560 KB
hand_02 WA 2 ms 2560 KB
hand_03 AC 2 ms 2560 KB