Есть задача:
https://codeforces.com/contest/1399/problem/E1
Вот код:
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
struct cmp {
bool operator() (const long long& a, const long long& b) const {
return a > b;
}
};
set<long long,cmp>se;
set<int>vis;
long long all = 0;
int dfs(int v,vector <vector<pair<int, int>>>& g) {
if (g[v].size() == 1&&v!=1) {
return 1;
}
int ans = 0;
for (auto c : g[v]) {
if (vis.find(c.first)==vis.end()) {
int cur = 0;
vis.insert(c.first);
cur+=dfs(c.first,g);// сколько листьев при переходе
se.insert(c.second* cur);
all += c.second * cur;
ans += cur;
}
}
return ans;// сколько листьев в поддереве с корнем в вершине v
}
int main() {
IOS;
int t;
cin >> t;
while (t--) {
all = 0;
se.clear();
vis.clear();
int n, s;
cin >> n >> s;
vector <vector<pair<int, int>>>g(n+1);
for (int i = 0; i < n - 1; i++) {
int v, u, w;
cin >> v >> u >> w;
g[v].push_back({ u,w });
g[u].push_back({ v,w });
}
vis.insert(1);
dfs(1,g);
long long ans = 0;
while (all > s) {
long long cur = *se.begin();
se.erase(cur);
ans++;
all -= cur;
all += cur / 2;
se.insert(cur/2);
}
cout << ans << "\n";
}
}
Получаю TL на 2-м тесте,почему не могу понять (возможно зависает решение).Заранее спасибо за помощь!
P.S Соревнование уже закончилось
Средний
