oj.uz

Submission #1091258

# Submission time Handle Problem Language Result Execution time Memory
1091258 2024-09-20T09:44:40 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(h[u] > mid) {
		if(mini > mid) {
			pos.push_back(u);
			cnt++;
			g[u] = 0;
			b[u] = -h[u];
		}
		else {
			g[u] = mini;
			b[u] = a.back();
		}
		return;
	}
	// if(a[0] > mid) {
		// cout << u << '\n';
		// //assert(1 == 2);
		// // 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:174:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |      freopen("file.inp", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Firefighting.cpp:175:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |      freopen("file.out", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 50436 KB Output is correct
2 Correct 305 ms 50372 KB Output is correct
3 Correct 83 ms 22348 KB Output is correct
4 Correct 284 ms 49416 KB Output is correct
5 Correct 3 ms 7512 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 4 ms 7380 KB Output is correct
3 Correct 4 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 3 ms 7512 KB Output is correct
7 Correct 4 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 4 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 3 ms 7456 KB Output is correct
12 Correct 4 ms 7516 KB Output is correct
13 Correct 3 ms 7532 KB Output is correct
14 Correct 3 ms 7472 KB Output is correct
15 Correct 5 ms 7516 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 7516 KB Output is correct
5 Correct 5 ms 7492 KB Output is correct
6 Correct 5 ms 7484 KB Output is correct
7 Correct 5 ms 7516 KB Output is correct
8 Correct 4 ms 7516 KB Output is correct
9 Correct 3 ms 7516 KB Output is correct
10 Correct 3 ms 7508 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 3 ms 7520 KB Output is correct
13 Correct 3 ms 7516 KB Output is correct
14 Correct 3 ms 7512 KB Output is correct
15 Correct 4 ms 7512 KB Output is correct
16 Correct 3 ms 7516 KB Output is correct
17 Correct 3 ms 7520 KB Output is correct
18 Correct 3 ms 7516 KB Output is correct
19 Correct 4 ms 7516 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 3 ms 7516 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 3 ms 7516 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 50240 KB Output is correct
2 Correct 117 ms 27556 KB Output is correct
3 Correct 119 ms 27976 KB Output is correct
4 Correct 100 ms 25412 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 204 ms 44500 KB Output is correct
8 Correct 205 ms 44212 KB Output is correct
9 Correct 209 ms 43988 KB Output is correct
10 Correct 232 ms 43960 KB Output is correct
11 Correct 274 ms 50260 KB Output is correct
12 Runtime error 165 ms 52376 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 15452 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 39692 KB Output is correct
2 Correct 206 ms 37172 KB Output is correct
3 Correct 257 ms 39392 KB Output is correct
4 Correct 80 ms 22612 KB Output is correct
5 Correct 301 ms 61512 KB Output is correct
6 Correct 308 ms 59204 KB Output is correct
7 Correct 313 ms 65456 KB Output is correct
8 Correct 323 ms 63876 KB Output is correct
9 Correct 285 ms 53444 KB Output is correct
10 Correct 277 ms 51636 KB Output is correct
11 Correct 300 ms 69128 KB Output is correct
12 Correct 139 ms 29592 KB Output is correct
13 Correct 325 ms 57528 KB Output is correct
14 Correct 361 ms 49732 KB Output is correct
15 Correct 276 ms 40304 KB Output is correct
16 Correct 236 ms 37968 KB Output is correct
17 Correct 230 ms 37712 KB Output is correct
18 Correct 266 ms 39760 KB Output is correct
19 Correct 148 ms 29940 KB Output is correct
20 Correct 71 ms 20308 KB Output is correct
21 Correct 234 ms 39676 KB Output is correct