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 |
× 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 |