Submission #261260

#	Time	Username	Problem	Language	Result	Execution time	Memory
261260		Berted	Firefighting (NOI20_firefighting)	C++14	100 / 100	580 ms	42664 KiB

Firefighting

#include <iostream>
#include <vector>
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define vi vector<int>
#define vpi vector<pii>
#define fst first
#define snd second
#define pub push_back
using namespace std;
int n;
vector<vpi> adj;
vector<int> ans;
ll k;
ll dfs(int u, int p, ll c)
{
	ll deepNonCover = 0, largeCover = -1;
	for (auto v : adj[u])
	{
		if (v.fst ^ p)
		{
			ll tp = dfs(v.fst, u, v.snd);
			if (tp < -1) {deepNonCover = max(deepNonCover, - tp - 1);}
			else {largeCover = max(tp, largeCover);}
		}
	}
	//cout << u << " " << deepNonCover << " " << largeCover << "\n";
	if (deepNonCover <= largeCover) {return max(-1LL, largeCover - c);}
	else 
	{
		if (deepNonCover + c > k || p == -1) 
		{
			ans.push_back(u + 1);
			//cout << "INS " << u << " " << k - c << "\n";
			return max(-1LL, k - c);
		}
		else {return - deepNonCover - c - 1;}
	}
}
int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {adj.pub(vpi());}
	for (int i = 0; i < n - 1; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		adj[u - 1].pub({v - 1, w});
		adj[v - 1].pub({u - 1, w});
	}
	dfs(0, -1, 0);
	
	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); i++)
	{
		cout<<ans[i];
		if (i < ans.size() - 1) {cout << " ";}
	}
	cout<<"\n";
	return 0;
}

Compilation message (stderr)

Firefighting.cpp: In function 'int main()':
Firefighting.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++)
                  ~~^~~~~~~~~~~~
Firefighting.cpp:58:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i < ans.size() - 1) {cout << " ";}
       ~~^~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26
• Subtask 6: 38 / 38