oj.uz

Submission #1091246

# Submission time Handle Problem Language Result Execution time Memory
1091246 2024-09-20T08:37:53 Z MinhTuan11 Firefighting (NOI20_firefighting) C++17
55 / 100
 256 ms 62936 KB 
#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

const int N = 3e5 + 5;
const int K = 1e2 + 5;
const int mod = 1e9 + 7;
const int inf = 1e18;

#define all(v) (v).begin(), (v).end()
#define pii pair<int, int> 

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

int n, f, h[N];
vector<pii> adj[N];
vector<int> pos;
int g[N], b[N], l, r, mid, cnt;

void pre(int u, int p) {
	for(pii w : adj[u]) {
		int v = w.fi, c = w.se;
		if(v == p) continue;
		h[v] = c;
		pre(v, u);
	}
}

void dfs(int u, int p) {
	vector<int> a;
	int mini = inf;
	for(pii w : adj[u]) {
		int v = w.fi, c = w.se;
		if(v == p) continue;
		dfs(v, u);
		a.push_back(b[v] + c);
		mini = min(mini, g[v] + c);
	}
	sort(all(a));
	if(a.size() == 0) {
		if(h[u] > mid) {
			// cout << "+ " << u << '\n';
			pos.push_back(u);
			cnt++;
			g[u] = 0;
			b[u] = -h[u];
		}
		else {
			g[u] = inf;
			b[u] = 0;
		}
		return;
	}
	if(u == 1) {
		// cout << u << ' ' << a.back() << ' ' << mini << '\n';
		if(mini > mid) {
			// cout << "+ " << u << '\n';
			pos.push_back(u);
			cnt++;
			return;
		}
		else {
			if(a.back() + mini > mid) {
				// cout << "+ " << u << '\n';
				pos.push_back(u);
				cnt++;
				return;
			}
		}
	}
	if(mini > mid) {
		// cout << u << ' ' << a.back() << ' ' << mini << '\n';
		if(a.back() + h[u] > mid) {
			// cout << "+ " << u << '\n';
			pos.push_back(u);
			cnt++;
			g[u] = 0;
			b[u] = -h[u];
		}
		else {
			g[u] = mini;
			b[u] = a.back();
		}
	}
	else {
		// cout << u << ' ' << a.back() << ' ' << mini << '\n';
		if(a.back() + h[u] > mid) {
			if(a.back() + mini > mid) {
				// cout << "+ " << u << '\n';
				pos.push_back(u);
				cnt++;
				g[u] = 0;
				b[u] = -h[u];
			}
			else {
				g[u] = mini;
				b[u] = 0;
			}
		}
		else {
			g[u] = mini;
			b[u] = a.back();
			if(a.back() + mini <= mid) b[u] = -h[u];
		}
	}
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    if(ifstream("file.inp")){
    	freopen("file.inp", "r", stdin);
    	freopen("file.out", "w", stdout);
    }
    
    cin >> n >> f;
    for(int i = 2; i <= n; i++) {
    	int j, t;
    	int x;
    	cin >> x;
    	cin >> j >> t;
    	adj[x].push_back({j, t});
    	adj[j].push_back({x, t});
    	r += t;
    	// cout << i << ' ' << j << ' ' << t << '\n';
    }
    mid = f;
    pre(1, 0);
    dfs(1, 0);
    // l = 3, r = 3;
    // int res = inf;
    // while(l <= r) {
    	// mid = l + r >> 1;
    	// cnt = 0;
    	// for(int i = 1; i <= n; i++) {
    		// g[i] = inf;
    	// }
    	// dfs(1, 0);
    	// // cout << "cnt: " << cnt << '\n';
    	// if(cnt <= f) {
    		// res = mid;
    		// r = mid - 1;
    	// }
    	// else l = mid + 1;
    // }
    // cout << res << '\n';
    if(cnt == 0) {
    	cnt++;
    	pos.push_back(1);
    }
    cout << cnt << '\n';
    for(int x : pos) cout << x << ' ';
    
    return 0;
}

// tuntun

Compilation message

Firefighting.cpp: In function 'int main()':
Firefighting.cpp:117:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |      freopen("file.inp", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Firefighting.cpp:118:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |      freopen("file.out", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 41704 KB Output is correct
2 Correct 218 ms 41776 KB Output is correct
3 Correct 57 ms 20164 KB Output is correct
4 Correct 205 ms 40892 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7512 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 41728 KB Output is correct
2 Correct 92 ms 24528 KB Output is correct
3 Correct 98 ms 24860 KB Output is correct
4 Correct 72 ms 22472 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 144 ms 39416 KB Output is correct
8 Correct 179 ms 40768 KB Output is correct
9 Correct 146 ms 39608 KB Output is correct
10 Correct 166 ms 39460 KB Output is correct
11 Correct 218 ms 41924 KB Output is correct
12 Incorrect 117 ms 28552 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 36464 KB Output is correct
2 Correct 162 ms 34824 KB Output is correct
3 Correct 201 ms 37320 KB Output is correct
4 Correct 72 ms 21016 KB Output is correct
5 Correct 226 ms 54576 KB Output is correct
6 Correct 243 ms 52040 KB Output is correct
7 Correct 250 ms 59128 KB Output is correct
8 Correct 250 ms 57296 KB Output is correct
9 Correct 225 ms 49096 KB Output is correct
10 Correct 222 ms 47560 KB Output is correct
11 Correct 256 ms 62936 KB Output is correct
12 Correct 97 ms 27436 KB Output is correct
13 Correct 215 ms 51132 KB Output is correct
14 Correct 221 ms 45928 KB Output is correct
15 Correct 180 ms 37460 KB Output is correct
16 Correct 165 ms 35408 KB Output is correct
17 Correct 164 ms 35156 KB Output is correct
18 Correct 190 ms 37188 KB Output is correct
19 Correct 138 ms 28264 KB Output is correct
20 Correct 60 ms 19280 KB Output is correct
21 Correct 193 ms 37336 KB Output is correct