@dalbio

Как исправить Tl?

Есть задача: 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 Соревнование уже закончилось
  • Вопрос задан
  • 93 просмотра
Решения вопроса 1
wataru
@wataru
Попробуйте читать через scanf.

Я вижу, вы делаете через sync_with_stdio(0), но я не уверен, что это 100% помогает.

Потом, вместо set vis достаточно передавать в dfs предыдущую вершину и не ходить в нее.

А еше у вас ошибка, при делении ребра пополам нельзя делить пополам cnt*w. Если cnt четное, а w нечетное, вы потереяете округление. Надо пихать в кучу пару cnt, w, и брать максимальное cnt*ceil(w/2). И еще, вы пихаете в кучу цену ребра, помноженную на количество листьев по этому ребру и всем предыдущем в текущей вершине! Надо там не cur брать, а значение dfs.

И еще, оно скорее всего виснет из-за переполнения. При умножении cur*c.second может получиться отрицательное число, вы же int-ы перемножаете, и только потом к long long приводите.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
v1t3man
@v1t3man
Смотрите разбор задач
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
27 сент. 2020, в 01:57
15000 руб./за проект
27 сент. 2020, в 00:32
20000 руб./за проект
26 сент. 2020, в 23:26
2000 руб./за проект