oj.uz

답안 #931273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
931273 2024-02-21T13:47:34 Z penguin133 Firefighting (NOI20_firefighting) C++17
22 / 100
 235 ms 46128 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;
	for(auto [i, j] : adj[x]){
		if(i == par)continue;
		dfs(i, x, j, cur + j);
		md[x] = min(md[x], md[i]);
		dp[x].fi += dp[i].fi;
		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:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main(){
      | ^~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 37576 KB Output is correct
2 Correct 203 ms 37540 KB Output is correct
3 Correct 57 ms 22472 KB Output is correct
4 Correct 204 ms 37132 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12888 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 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 4 ms 13088 KB Output is correct
9 Incorrect 2 ms 12892 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12888 KB Output is correct
4 Correct 2 ms 12892 KB Output is correct
5 Correct 2 ms 12892 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 2 ms 12892 KB Output is correct
8 Correct 2 ms 12892 KB Output is correct
9 Correct 2 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 Incorrect 3 ms 12900 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 38340 KB Output is correct
2 Correct 84 ms 25236 KB Output is correct
3 Correct 101 ms 25300 KB Output is correct
4 Correct 71 ms 24148 KB Output is correct
5 Correct 3 ms 12912 KB Output is correct
6 Correct 3 ms 12952 KB Output is correct
7 Correct 161 ms 41724 KB Output is correct
8 Correct 154 ms 40632 KB Output is correct
9 Correct 164 ms 40964 KB Output is correct
10 Correct 159 ms 40628 KB Output is correct
11 Correct 217 ms 46128 KB Output is correct
12 Correct 118 ms 31460 KB Output is correct
13 Correct 61 ms 25032 KB Output is correct
14 Correct 135 ms 30408 KB Output is correct
15 Correct 149 ms 34220 KB Output is correct
16 Correct 182 ms 35788 KB Output is correct
17 Correct 119 ms 31944 KB Output is correct
18 Correct 133 ms 31436 KB Output is correct

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 12892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 194 ms 32336 KB Output isn't correct
2 Halted 0 ms 0 KB -