Submission #3418551
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]--; } else { revs[v]++; } int tmp; if (d[u][0].second == v) { tmp = d[u].size() == 1 ? 1 : d[u][1].first + 1; } else { tmp = d[u][0].first + 1; } d[v].push_back({tmp, 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 | 1811 Byte |
Status | WA |
Exec Time | 135 ms |
Memory | 29824 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 700 | ||||||
Status |
|
|
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 | 58 ms | 8448 KB |
01_random_02 | WA | 120 ms | 16640 KB |
01_random_03 | WA | 54 ms | 7936 KB |
01_random_04 | WA | 75 ms | 10752 KB |
01_random_05 | WA | 69 ms | 9984 KB |
01_random_06 | WA | 6 ms | 1024 KB |
01_random_07 | WA | 93 ms | 13184 KB |
01_random_08 | WA | 61 ms | 8832 KB |
01_random_09 | WA | 103 ms | 14464 KB |
02_path_00 | WA | 128 ms | 25984 KB |
02_path_01 | WA | 135 ms | 26752 KB |
02_path_02 | WA | 126 ms | 24704 KB |
02_path_03 | WA | 127 ms | 25088 KB |
02_path_04 | WA | 130 ms | 28416 KB |
02_path_05 | WA | 128 ms | 29568 KB |
02_path_06 | AC | 122 ms | 23808 KB |
02_path_07 | WA | 130 ms | 26624 KB |
02_path_08 | WA | 131 ms | 28928 KB |
02_path_09 | WA | 127 ms | 26624 KB |
02_path_10 | AC | 128 ms | 29824 KB |
02_path_11 | WA | 125 ms | 26752 KB |
02_path_12 | WA | 127 ms | 28800 KB |
02_path_13 | WA | 129 ms | 26880 KB |
02_path_14 | WA | 126 ms | 24960 KB |
03_uni_00 | WA | 107 ms | 16624 KB |
03_uni_01 | WA | 107 ms | 17136 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 | 107 ms | 17136 KB |
03_uni_06 | WA | 104 ms | 16624 KB |
03_uni_07 | WA | 107 ms | 16624 KB |
03_uni_08 | WA | 108 ms | 16624 KB |
03_uni_09 | WA | 101 ms | 16624 KB |
03_uni_10 | WA | 108 ms | 16624 KB |
03_uni_11 | WA | 107 ms | 16624 KB |
03_uni_12 | WA | 110 ms | 16624 KB |
03_uni_13 | WA | 115 ms | 16624 KB |
03_uni_14 | WA | 107 ms | 16624 KB |
hand_00 | WA | 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 |