oj.uz

Submission #931274

# Submission time Handle Problem Language Result Execution time Memory
931274 2024-02-21T13:51:07 Z penguin133 Firefighting (NOI20_firefighting) C++17
100 / 100
 315 ms 69448 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

pi dp[300005]; // no of stuff, max dist of a node not alr covered by fire
int md[300005], dep[300005];
int n, k;
vector <pi> adj[300005];
vector <int> ans;

void dfs(int x, int par, int w, int cur){
	dep[x] = cur;
	md[x] = 1e18;
	int mx = -1e18;
	multiset <int> ms;
	for(auto [i, j] : adj[x]){
		if(i == par)continue;
		
		dfs(i, x, j, cur + j);
		ms.insert(md[i]);
	}
	for(auto [i, j] : adj[x]){
		if(i == par)continue;
		md[x] = min(md[x], md[i]);
		dp[x].fi += dp[i].fi;
		if(dp[i].se + j + *ms.begin() - dep[x] > k)mx = max(mx, dp[i].se + j);
	}
	int tmp = md[x] - dep[x];
	if(tmp > k)mx = max(mx, 0ll);
	dp[x].se = mx;
	if(mx + w > k && mx >= 0){
		ans.push_back(x);
		md[x] = dep[x];
		dp[x].fi++;
		dp[x].se = -1e18;
	}
}

void solve(){
	cin >> n >> k;
	for(int i = 1; i < n; i++){
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c}); adj[b].push_back({a, c});
	}
	dfs(1, -1, 1e18, 0);
	cout << (int)ans.size() << '\n';
	for(auto i : ans)cout << i << ' ';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

Firefighting.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main(){
      | ^~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 37864 KB Output is correct
2 Correct 226 ms 38336 KB Output is correct
3 Correct 55 ms 22724 KB Output is correct
4 Correct 220 ms 38096 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 13048 KB Output is correct
9 Correct 2 ms 12892 KB Output is correct
10 Correct 2 ms 13144 KB Output is correct
11 Correct 3 ms 12936 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 2 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 2 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 3 ms 12892 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 2 ms 12892 KB Output is correct
12 Correct 2 ms 12892 KB Output is correct
13 Correct 3 ms 12892 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 2 ms 12892 KB Output is correct
16 Correct 3 ms 12892 KB Output is correct
17 Correct 2 ms 12892 KB Output is correct
18 Correct 2 ms 12892 KB Output is correct
19 Correct 2 ms 12892 KB Output is correct
20 Correct 2 ms 12892 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 2 ms 12900 KB Output is correct
23 Correct 3 ms 12892 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12892 KB Output is correct
26 Correct 4 ms 12888 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 38352 KB Output is correct
2 Correct 91 ms 25312 KB Output is correct
3 Correct 92 ms 25544 KB Output is correct
4 Correct 75 ms 24144 KB Output is correct
5 Correct 2 ms 12888 KB Output is correct
6 Correct 3 ms 12888 KB Output is correct
7 Correct 204 ms 41304 KB Output is correct
8 Correct 259 ms 41200 KB Output is correct
9 Correct 246 ms 41952 KB Output is correct
10 Correct 224 ms 41824 KB Output is correct
11 Correct 254 ms 38704 KB Output is correct
12 Correct 121 ms 28372 KB Output is correct
13 Correct 98 ms 23236 KB Output is correct
14 Correct 110 ms 27332 KB Output is correct
15 Correct 175 ms 30616 KB Output is correct
16 Correct 167 ms 31728 KB Output is correct
17 Correct 148 ms 28584 KB Output is correct
18 Correct 125 ms 28144 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 13148 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12952 KB Output is correct
5 Correct 4 ms 13320 KB Output is correct
6 Correct 4 ms 13404 KB Output is correct
7 Correct 4 ms 13204 KB Output is correct
8 Correct 4 ms 13148 KB Output is correct
9 Correct 4 ms 13148 KB Output is correct
10 Correct 3 ms 13148 KB Output is correct
11 Correct 4 ms 13148 KB Output is correct
12 Correct 3 ms 12892 KB Output is correct
13 Correct 4 ms 13404 KB Output is correct
14 Correct 3 ms 13148 KB Output is correct
15 Correct 4 ms 13148 KB Output is correct
16 Correct 3 ms 12904 KB Output is correct
17 Correct 3 ms 12888 KB Output is correct
18 Correct 3 ms 13148 KB Output is correct
19 Correct 3 ms 12892 KB Output is correct
20 Correct 3 ms 12892 KB Output is correct
21 Correct 3 ms 13204 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 32340 KB Output is correct
2 Correct 217 ms 37584 KB Output is correct
3 Correct 203 ms 39440 KB Output is correct
4 Correct 63 ms 25428 KB Output is correct
5 Correct 256 ms 60736 KB Output is correct
6 Correct 261 ms 57920 KB Output is correct
7 Correct 294 ms 66844 KB Output is correct
8 Correct 263 ms 64448 KB Output is correct
9 Correct 234 ms 54776 KB Output is correct
10 Correct 258 ms 53376 KB Output is correct
11 Correct 315 ms 69448 KB Output is correct
12 Correct 146 ms 30704 KB Output is correct
13 Correct 261 ms 56684 KB Output is correct
14 Correct 240 ms 50516 KB Output is correct
15 Correct 224 ms 39760 KB Output is correct
16 Correct 258 ms 38148 KB Output is correct
17 Correct 232 ms 37976 KB Output is correct
18 Correct 204 ms 39720 KB Output is correct
19 Correct 181 ms 31292 KB Output is correct
20 Correct 74 ms 23920 KB Output is correct
21 Correct 222 ms 39680 KB Output is correct