oj.uz

Submission #333227

# Submission time Handle Problem Language Result Execution time Memory
333227 2020-12-05T01:39:47 Z Cantfindme Firefighting (NOI20_firefighting) C++17
100 / 100
 367 ms 44892 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
const int maxn = 300010;
const int INF = LLONG_MAX/3;

int n,k;
vector <pi> adjlist[maxn];
vector <int> ans;

int dfs(int x, int p, int d) {
	int maxover = -INF, minunder = 0;
	for (auto i: adjlist[x]) if (i.f != p) {
		int res = dfs(i.f,x,i.s);
		if (res < 0) minunder = min(minunder,res);
		else if (res > 0) maxover = max(maxover,res - i.s);
	}
	
	int res = 0;
	if (maxover < abs(minunder)) { 
		if (abs(minunder) + d <= k) { //delay. Underflow
			res = -(abs(minunder) + d);
		} else { //Build here. overflow.
			ans.push_back(x);
			res = k;
		}
	} else if (maxover >= abs(minunder)) {
		res = maxover;
	}
	return res;
}

int32_t main() {
	FAST	
	cin >> n >> k;
	for (int i =0;i<n-1;i++) {
		int a,b,d; cin >> a >> b >> d;
		adjlist[a].push_back(pi(b,d));
		adjlist[b].push_back(pi(a,d));
	}
	
	dfs(1,-1,INF);
	cout << ans.size() << "\n";
	for (auto i: ans) cout << i << " ";
	
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 34780 KB Output is correct
2 Correct 363 ms 34644 KB Output is correct
3 Correct 119 ms 17376 KB Output is correct
4 Correct 344 ms 34012 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 6 ms 7404 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 34652 KB Output is correct
2 Correct 170 ms 20324 KB Output is correct
3 Correct 180 ms 20836 KB Output is correct
4 Correct 152 ms 18916 KB Output is correct
5 Correct 5 ms 7404 KB Output is correct
6 Correct 6 ms 7404 KB Output is correct
7 Correct 269 ms 31060 KB Output is correct
8 Correct 271 ms 30932 KB Output is correct
9 Correct 266 ms 31060 KB Output is correct
10 Correct 263 ms 31324 KB Output is correct
11 Correct 359 ms 34780 KB Output is correct
12 Correct 214 ms 23680 KB Output is correct
13 Correct 118 ms 17420 KB Output is correct
14 Correct 201 ms 22752 KB Output is correct
15 Correct 244 ms 25696 KB Output is correct
16 Correct 263 ms 26984 KB Output is correct
17 Correct 217 ms 23912 KB Output is correct
18 Correct 207 ms 23520 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7532 KB Output is correct
2 Correct 6 ms 7532 KB Output is correct
3 Correct 5 ms 7532 KB Output is correct
4 Correct 6 ms 7532 KB Output is correct
5 Correct 7 ms 7788 KB Output is correct
6 Correct 7 ms 7788 KB Output is correct
7 Correct 7 ms 7788 KB Output is correct
8 Correct 7 ms 7788 KB Output is correct
9 Correct 7 ms 7660 KB Output is correct
10 Correct 7 ms 7660 KB Output is correct
11 Correct 8 ms 7788 KB Output is correct
12 Correct 6 ms 7532 KB Output is correct
13 Correct 7 ms 7788 KB Output is correct
14 Correct 6 ms 7660 KB Output is correct
15 Correct 7 ms 7660 KB Output is correct
16 Correct 6 ms 7532 KB Output is correct
17 Correct 6 ms 7532 KB Output is correct
18 Correct 6 ms 7660 KB Output is correct
19 Correct 6 ms 7532 KB Output is correct
20 Correct 6 ms 7532 KB Output is correct
21 Correct 7 ms 7660 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 29744 KB Output is correct
2 Correct 286 ms 28396 KB Output is correct
3 Correct 306 ms 30060 KB Output is correct
4 Correct 129 ms 17888 KB Output is correct
5 Correct 331 ms 40412 KB Output is correct
6 Correct 323 ms 39260 KB Output is correct
7 Correct 313 ms 42832 KB Output is correct
8 Correct 318 ms 41764 KB Output is correct
9 Correct 320 ms 36836 KB Output is correct
10 Correct 315 ms 36068 KB Output is correct
11 Correct 329 ms 44892 KB Output is correct
12 Correct 200 ms 22636 KB Output is correct
13 Correct 324 ms 38752 KB Output is correct
14 Correct 328 ms 35428 KB Output is correct
15 Correct 310 ms 30316 KB Output is correct
16 Correct 294 ms 28780 KB Output is correct
17 Correct 283 ms 28652 KB Output is correct
18 Correct 310 ms 30188 KB Output is correct
19 Correct 216 ms 23276 KB Output is correct
20 Correct 111 ms 16364 KB Output is correct
21 Correct 319 ms 30188 KB Output is correct