oj.uz

Submission #1091254

# Submission time Handle Problem Language Result Execution time Memory
1091254 2024-09-20T09:33:22 Z MinhTuan11 Firefighting (NOI20_firefighting) C++17
55 / 100
 361 ms 69128 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 291 ms 50236 KB Output is correct
2 Correct 293 ms 50308 KB Output is correct
3 Correct 84 ms 22280 KB Output is correct
4 Correct 272 ms 49476 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct

Subtask #2
5.0 / 5.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 7516 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 4 ms 7516 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 5 ms 7516 KB Output is correct
10 Correct 4 ms 7516 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 5 ms 7516 KB Output is correct
13 Correct 3 ms 7516 KB Output is correct
14 Correct 4 ms 7516 KB Output is correct
15 Correct 3 ms 7376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 5 ms 7516 KB Output is correct
4 Correct 3 ms 7496 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 5 ms 7460 KB Output is correct
7 Correct 4 ms 7512 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 3 ms 7768 KB Output is correct
10 Correct 3 ms 7512 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 3 ms 7476 KB Output is correct
14 Correct 5 ms 7516 KB Output is correct
15 Correct 3 ms 7536 KB Output is correct
16 Correct 3 ms 7516 KB Output is correct
17 Correct 4 ms 7516 KB Output is correct
18 Correct 4 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 3 ms 7520 KB Output is correct
22 Correct 3 ms 7516 KB Output is correct
23 Correct 4 ms 7396 KB Output is correct
24 Correct 3 ms 7516 KB Output is correct
25 Correct 3 ms 7512 KB Output is correct
26 Correct 3 ms 7512 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 50428 KB Output is correct
2 Correct 125 ms 27464 KB Output is correct
3 Correct 126 ms 27972 KB Output is correct
4 Correct 102 ms 25412 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 220 ms 44528 KB Output is correct
8 Correct 238 ms 43960 KB Output is correct
9 Correct 225 ms 43876 KB Output is correct
10 Correct 230 ms 43960 KB Output is correct
11 Correct 302 ms 50444 KB Output is correct
12 Incorrect 152 ms 33092 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 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 303 ms 39744 KB Output is correct
2 Correct 218 ms 37096 KB Output is correct
3 Correct 244 ms 39508 KB Output is correct
4 Correct 86 ms 22228 KB Output is correct
5 Correct 331 ms 61572 KB Output is correct
6 Correct 290 ms 59204 KB Output is correct
7 Correct 361 ms 65452 KB Output is correct
8 Correct 280 ms 63940 KB Output is correct
9 Correct 288 ms 53284 KB Output is correct
10 Correct 267 ms 51844 KB Output is correct
11 Correct 286 ms 69128 KB Output is correct
12 Correct 138 ms 29464 KB Output is correct
13 Correct 291 ms 57528 KB Output is correct
14 Correct 319 ms 49768 KB Output is correct
15 Correct 276 ms 40416 KB Output is correct
16 Correct 224 ms 37972 KB Output is correct
17 Correct 265 ms 37652 KB Output is correct
18 Correct 245 ms 40024 KB Output is correct
19 Correct 137 ms 30036 KB Output is correct
20 Correct 73 ms 20220 KB Output is correct
21 Correct 250 ms 39764 KB Output is correct