#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;//find_by_order(ind);
//order_of_key()
#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define yes "YES"
#define no "NO"
#define bigg INT_MAX
#define debug(x) cout<<(#x)<<" = " <<x<<endl;
#define all(x) x.begin(),x.end()
#define sz size()
#define nn '\n'
#define mms(x,y) memset(x,y,sizeof(x))
#define forr(i,j,n) for (int i=j; i<n; i++)
#define forn(i,j,n) for (int i=j; i>n; i--)
#define fi first
#define se second
#define la "LA"
#define cinn(x,y) for(int i=0; i<y; i++) cin>>x[i];
#define pii pair<int,int>
vector<pii> a[300001];
priority_queue<pii> q;
bool vis[300001]={ };
void dfs(int x, int cover)
{
//cout<<"HA"<<x<<' '<<cover<<endl;
vis[x]=1;
for(auto y:a[x])
{
if (vis[y.fi]) continue;
if (cover>=y.se)
{
dfs(y.fi,cover-y.se);
}
else
{
q.push({0,y.fi});
// cout<<"NOOOOO"<<y.fi<<endl;
}
}
return;
}
signed main()
{
// #ifndef LOCAL
// freopen("lifeguards.in","r",stdin);
// freopen("lifeguards.out","w", stdout);
// #endif
fast
int n,k;
cin>>n >>k;
forr(i,0,n-1)
{
int x,y,z;
cin>>x >>y >>z;
a[x].pb({y,z});
a[y].pb({x,z});
}
forr(i,1,n+1)
{
if (a[i].sz==1) q.push({0,i});
}
vector<int> ans;
while(!q.empty())
{
int last=q.top().fi;
int x=q.top().se;
q.pop();
if (vis[x]) continue;
//cout<<x<<' '<<last<<endl;
vis[x]=1;
int mx=0;
bool f=0;
for(auto w:a[x])
{
int y=w.fi;
int z=w.se;
if (vis[y]) continue;
if (z>k) {
//cout<<la<<x<<' '<<y<<endl;
q.push({0,y});}
else if ((z+last)>k)
{
mx=max(mx,z);
f=1;
}
else
{
f=1;
}
}
if (f==0)
{
ans.pb(x);
}
else if (mx==0)
{
for(auto w:a[x])
{
int y=w.fi;
int z=w.se;
if(vis[y]) continue;
if (z<=k) q.push({z+last,y});
}
}
else
{
ans.pb(x);
for(auto w:a[x])
{
int y=w.fi;
int z=w.se;
if (vis[y]) continue;
if (z<=k)
{
// cout<<y<<endl;
dfs(y,k-z);
// int cur=y;
// while()
}
}
}
}
cout<<ans.sz<<nn;
for(auto p:ans) cout<<p<<' ';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
269 ms |
39760 KB |
Output is correct |
2 |
Correct |
234 ms |
40628 KB |
Output is correct |
3 |
Correct |
76 ms |
18284 KB |
Output is correct |
4 |
Correct |
243 ms |
38608 KB |
Output is correct |
5 |
Correct |
2 ms |
7516 KB |
Output is correct |
6 |
Incorrect |
2 ms |
7516 KB |
Integer parameter [name=F] equals to 0, violates the range [1, 1] |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
7516 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7728 KB |
Output is correct |
2 |
Correct |
2 ms |
7620 KB |
Output is correct |
3 |
Incorrect |
2 ms |
7516 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
287 ms |
42672 KB |
Output is correct |
2 |
Incorrect |
97 ms |
22804 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
7768 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
205 ms |
32632 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |