Submission #2067933
Source Code Expand
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define pr1(a) (#a)<<"="<<(a)
#define pr2(a,b) pr1(a)<<", "<<pr1(b)
#define pr3(a,b,c) pr2(a,b)<<", "<<pr1(c)
#define pr4(a,b,c,d) pr3(a,b,c)<<", "<<pr1(d)
#define pr5(a,b,c,d,e) pr4(a,b,c,d)<<", "<<pr1(e)
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}
typedef pair<P,int> PP;
int n,L;
vector<vector<PP> > G;
vector<vector<P> >D;
vector<int> C;
int dfs1(int pos,int pre){
for(auto p:G[pos]){
int to,cost;
tie(to,cost) = p.first;
if(to == pre) continue;
D[pos].push_back(P(cost+dfs1(to,pos),to));
}
if(D[pos].size() == 0) D[pos].push_back(P(0,-1));
sort(D[pos].begin(),D[pos].end(),greater<P>());
return D[pos][0].first;
}
void dfs2(int pos,int pre){
if(D[pos].size() == 0) D[pos].push_back(P(0,-1));
auto Push=[&](int to,int cost){
int a = D[pos][0].second;
D[to].push_back(P(D[pos][to == a].first+cost,pos));
sort(D[to].begin(),D[to].end(),greater<P>());
};
for(auto p:G[pos]){
int to,cost;
tie(to,cost) = p.first;
if(to == pre) continue;
Push(to,cost);
dfs2(to,pos);
}
}
int dfs3(int pos,int pre=-1){
if(pre != -1 && G[pos].size() == 1) return C[pos] = 0;
int res = 0;
for(auto p:G[pos]){
int to = p.first.first;
int dir = p.second;
if(to == pre) continue;
res += (dir == 0) + dfs3(to,pos);
}
return C[pos] = res;
}
int dfs4(int pos,int pre){
auto update=[&](int to,int dir){
C[to] = dir == 0? C[pos]-1:C[pos]+1;
};
int res = D[pos][0].first<=L? C[pos]:INF;
for(auto p:G[pos]){
int to = p.first.first;
int dir = p.second;
if(to == pre) continue;
update(to,dir);
Min(res,dfs4(to,pos));
}
return res;
}
signed main(){
cin>>n>>L;
G.resize(n);
D.resize(n);
C.resize(n);
for(int i=0;i<n-1;i++){
int a,b,c;
cin>>a>>b>>c; a--,b--;
G[a].push_back(PP(P(b,c),0));
G[b].push_back(PP(P(a,c),1));
}
dfs1(0,-1);
dfs2(0,-1);
dfs3(0,-1);
int ans = dfs4(0,-1);
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - 限界集落 |
User |
haji |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2944 Byte |
Status |
WA |
Exec Time |
153 ms |
Memory |
26880 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 |
AC |
38 ms |
5504 KB |
01_random_01 |
AC |
63 ms |
8960 KB |
01_random_02 |
AC |
132 ms |
17536 KB |
01_random_03 |
AC |
59 ms |
8320 KB |
01_random_04 |
AC |
81 ms |
11392 KB |
01_random_05 |
AC |
75 ms |
10496 KB |
01_random_06 |
AC |
6 ms |
1024 KB |
01_random_07 |
AC |
102 ms |
13952 KB |
01_random_08 |
AC |
66 ms |
9344 KB |
01_random_09 |
AC |
114 ms |
15232 KB |
02_path_00 |
AC |
126 ms |
23936 KB |
02_path_01 |
AC |
129 ms |
24448 KB |
02_path_02 |
AC |
153 ms |
23040 KB |
02_path_03 |
AC |
130 ms |
23296 KB |
02_path_04 |
AC |
132 ms |
25856 KB |
02_path_05 |
AC |
129 ms |
26752 KB |
02_path_06 |
WA |
132 ms |
22272 KB |
02_path_07 |
AC |
137 ms |
24448 KB |
02_path_08 |
AC |
133 ms |
26112 KB |
02_path_09 |
AC |
130 ms |
24448 KB |
02_path_10 |
WA |
132 ms |
26880 KB |
02_path_11 |
AC |
131 ms |
24448 KB |
02_path_12 |
AC |
128 ms |
26112 KB |
02_path_13 |
AC |
126 ms |
24576 KB |
02_path_14 |
AC |
129 ms |
23168 KB |
03_uni_00 |
AC |
120 ms |
17456 KB |
03_uni_01 |
AC |
117 ms |
17456 KB |
03_uni_02 |
AC |
121 ms |
17968 KB |
03_uni_03 |
AC |
122 ms |
17968 KB |
03_uni_04 |
AC |
117 ms |
17456 KB |
03_uni_05 |
AC |
121 ms |
18224 KB |
03_uni_06 |
AC |
116 ms |
17456 KB |
03_uni_07 |
AC |
120 ms |
17456 KB |
03_uni_08 |
AC |
124 ms |
17456 KB |
03_uni_09 |
AC |
116 ms |
17456 KB |
03_uni_10 |
AC |
124 ms |
17968 KB |
03_uni_11 |
AC |
122 ms |
17456 KB |
03_uni_12 |
AC |
123 ms |
17456 KB |
03_uni_13 |
AC |
117 ms |
17456 KB |
03_uni_14 |
AC |
123 ms |
17712 KB |
hand_00 |
WA |
1 ms |
256 KB |
hand_01 |
AC |
1 ms |
256 KB |
hand_02 |
AC |
1 ms |
256 KB |
hand_03 |
AC |
1 ms |
256 KB |