oj.uz

Submission #1091255

# Submission time Handle Problem Language Result Execution time Memory
1091255 2024-09-20T09:36:30 Z MinhTuan11 Firefighting (NOI20_firefighting) C++17
55 / 100
 334 ms 69156 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);
		// cout << v << ' ' << b[v] << '\n';
		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;
			}
		}
		return;
	}
	if(a[0] > mid) {
		// 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(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];
		}
	}
}

namespace checker {
	bool check() {
		priority_queue<pii, vector<pii>, greater<pii>> q;
		vector<int> d(n + 1, inf);
		for(int x : pos) {
			q.push({0, x});
			d[x] = 0;
		}
		while(q.size()) {
			int y = q.top().se;
			int dy = q.top().fi;
			q.pop();
			if(dy > d[y]) continue;
			if(dy > mid) return 0;
			// cout << y << ' ' << d[y] << '\n';
			for(pii z : adj[y]) {
				if(d[z.fi] > d[y] + z.se) {
					d[z.fi] = d[y] + z.se;
					q.push({d[z.fi], z.fi});
				}
			}
		}
		return 1;
	}
}

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);
    }
    if(!checker::check()) {
    	assert(1 == 2);
    }
    cout << cnt << '\n';
    for(int x : pos) cout << x << ' ';
    
    return 0;
}

// tuntun

Compilation message

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 49976 KB Output is correct
2 Correct 299 ms 49976 KB Output is correct
3 Correct 79 ms 22344 KB Output is correct
4 Correct 266 ms 48968 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 4 ms 7516 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 3 ms 7320 KB Output is correct
4 Correct 5 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 5 ms 7520 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 3 ms 7524 KB Output is correct
10 Correct 3 ms 7512 KB Output is correct
11 Correct 4 ms 7516 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 5 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 7516 KB Output is correct
4 Correct 3 ms 7520 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7512 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 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 4 ms 7516 KB Output is correct
12 Correct 3 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 5 ms 7516 KB Output is correct
16 Correct 3 ms 7512 KB Output is correct
17 Correct 4 ms 7516 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 4 ms 7512 KB Output is correct
20 Correct 3 ms 7516 KB Output is correct
21 Correct 3 ms 7516 KB Output is correct
22 Correct 3 ms 7516 KB Output is correct
23 Correct 3 ms 7516 KB Output is correct
24 Correct 4 ms 7516 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 3 ms 7528 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 50004 KB Output is correct
2 Correct 119 ms 27376 KB Output is correct
3 Correct 126 ms 27976 KB Output is correct
4 Correct 111 ms 25416 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7484 KB Output is correct
7 Correct 197 ms 44284 KB Output is correct
8 Correct 209 ms 43960 KB Output is correct
9 Correct 222 ms 43704 KB Output is correct
10 Correct 223 ms 43700 KB Output is correct
11 Correct 270 ms 49984 KB Output is correct
12 Incorrect 159 ms 33340 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 270 ms 39480 KB Output is correct
2 Correct 215 ms 36696 KB Output is correct
3 Correct 264 ms 39300 KB Output is correct
4 Correct 82 ms 22356 KB Output is correct
5 Correct 309 ms 61300 KB Output is correct
6 Correct 286 ms 58948 KB Output is correct
7 Correct 284 ms 65324 KB Output is correct
8 Correct 295 ms 63772 KB Output is correct
9 Correct 272 ms 53188 KB Output is correct
10 Correct 266 ms 51588 KB Output is correct
11 Correct 285 ms 69156 KB Output is correct
12 Correct 169 ms 29392 KB Output is correct
13 Correct 334 ms 57344 KB Output is correct
14 Correct 303 ms 49484 KB Output is correct
15 Correct 247 ms 39884 KB Output is correct
16 Correct 237 ms 37396 KB Output is correct
17 Correct 212 ms 37200 KB Output is correct
18 Correct 270 ms 39400 KB Output is correct
19 Correct 145 ms 29780 KB Output is correct
20 Correct 74 ms 20240 KB Output is correct
21 Correct 230 ms 39164 KB Output is correct