Submission #3418607


Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define REP(i, n) for (ll (i) = 0; (i) < (n); (i)++)
#define REPI(i, a, b) for (ll (i) = (a); (i) < (b); (i)++)
#define int long long
using namespace std;
using II = pair<int, int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
const int MOD = 1e9 + 7;
const int HOGE = 1e4;

struct edge { int to, cost; };
signed main() {
  int N, D; cin >> N >> D;
  vector<vector<edge>> G(N);
  REP (i, N - 1) {
    int a, b, c; cin >> a >> b >> c;
    a--; b--;
    G[a].push_back({b, c});
    G[b].push_back({a, c + HOGE});
  }
  VI revs(N), strs(N);
  vector<vector<II>> d(N); // {cost_sum, v}
  VI far(N);
  function<void (int, int)> dfs1 = [&](int u, int prev) {
    for (edge e: G[u]) if (e.to != prev) {
      int v = e.to;
      dfs1(v, u);
      revs[u] += revs[v];
      strs[u] += strs[v];
      (e.cost >= HOGE ? revs[u] : strs[u])++;

      int tmp = far[v] + e.cost % HOGE;
      d[u].push_back({tmp, v});
      far[u] = max(far[u], tmp);
    }
  };
  dfs1(0, -1);

  sort(d[0].rbegin(), d[0].rend());
  function<void (int, int)> dfs2 = [&](int u, int prev) {
    for (edge e: G[u]) if (e.to != prev) {
      int v = e.to;
      revs[v] = revs[u];
      strs[v] = strs[u];
      if (e.cost >= HOGE) {
        revs[v]--; strs[v]++;
      } else {
        revs[v]++; strs[v]--;
      }
      assert(strs[v] + revs[v] == N - 1);

      int tmp;
      if (d[u][0].second == v) {
        tmp = d[u].size() == 1 ? 0 : d[u][1].first;
      } else {
        tmp = d[u][0].first;
      }
      d[v].push_back({tmp + e.cost % HOGE, u});
      sort(d[v].rbegin(), d[v].rend());
      dfs2(v, u);
    }
  };
  dfs2(0, -1);

  int ans = 1e7;
  REP (i, N) {
    if (d[i][0].first <= D) {
      ans = min(ans, revs[i]);
    }
  }
  cout << (ans == 1e7 ? -1 : ans) << endl;
}

Submission Info

Submission Time
Task E - 限界集落
User knshnb
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1909 Byte
Status WA
Exec Time 138 ms
Memory 29824 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 1
AC × 6
WA × 39
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 1 ms 256 KB
01_random_00 WA 35 ms 5248 KB
01_random_01 WA 57 ms 8448 KB
01_random_02 WA 120 ms 16640 KB
01_random_03 WA 54 ms 7936 KB
01_random_04 WA 74 ms 10752 KB
01_random_05 WA 69 ms 9984 KB
01_random_06 WA 6 ms 1024 KB
01_random_07 WA 96 ms 13184 KB
01_random_08 WA 60 ms 8832 KB
01_random_09 WA 102 ms 14464 KB
02_path_00 WA 128 ms 25984 KB
02_path_01 WA 129 ms 26752 KB
02_path_02 WA 127 ms 24704 KB
02_path_03 WA 125 ms 25088 KB
02_path_04 WA 132 ms 28416 KB
02_path_05 WA 138 ms 29568 KB
02_path_06 AC 125 ms 23808 KB
02_path_07 WA 126 ms 26624 KB
02_path_08 WA 135 ms 28928 KB
02_path_09 WA 130 ms 26624 KB
02_path_10 AC 134 ms 29824 KB
02_path_11 WA 129 ms 26752 KB
02_path_12 WA 132 ms 28800 KB
02_path_13 WA 132 ms 26880 KB
02_path_14 WA 126 ms 24960 KB
03_uni_00 WA 108 ms 16624 KB
03_uni_01 WA 108 ms 16624 KB
03_uni_02 WA 108 ms 16624 KB
03_uni_03 WA 108 ms 16620 KB
03_uni_04 WA 108 ms 16624 KB
03_uni_05 WA 108 ms 16624 KB
03_uni_06 WA 104 ms 16624 KB
03_uni_07 WA 108 ms 16624 KB
03_uni_08 WA 108 ms 16624 KB
03_uni_09 WA 103 ms 16624 KB
03_uni_10 WA 108 ms 16624 KB
03_uni_11 WA 107 ms 16624 KB
03_uni_12 WA 108 ms 16624 KB
03_uni_13 WA 110 ms 16624 KB
03_uni_14 WA 108 ms 16624 KB
hand_00 AC 1 ms 256 KB
hand_01 AC 1 ms 256 KB
hand_02 WA 1 ms 256 KB
hand_03 AC 1 ms 256 KB