oj.uz

Submission #1091261

# Submission time Handle Problem Language Result Execution time Memory
1091261 2024-09-20T09:54:31 Z MinhTuan11 Firefighting (NOI20_firefighting) C++17
74 / 100
 318 ms 63488 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) {
	// cout << u << '\n';
	vector<int> a;
	int mini = inf;
	for(pii w : adj[u]) {
		int v = w.fi, c = w.se;
		if(c > mid) continue;
		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 || h[u] > mid) {
		// 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] = 0;
		// }
		// 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);
    for(int i = 1; i <= n; i++) {
    	int pcnt = cnt;
    	if(i == 1 || h[i] > mid) {
    		dfs(i, 0);
    		if(cnt == pcnt) {
    			cnt++;
    			pos.push_back(i);
    		}
    	}
    }
    // 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:176:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |      freopen("file.inp", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Firefighting.cpp:177:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |      freopen("file.out", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 43388 KB Output is correct
2 Correct 214 ms 43324 KB Output is correct
3 Correct 61 ms 19784 KB Output is correct
4 Correct 191 ms 42716 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 4 ms 7272 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7292 KB Output is correct
4 Correct 4 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 7364 KB Output is correct
8 Correct 3 ms 7512 KB Output is correct
9 Correct 3 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 4 ms 7516 KB Output is correct
14 Correct 3 ms 7516 KB Output is correct
15 Correct 3 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 4 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 3 ms 7528 KB Output is correct
5 Correct 4 ms 7372 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 7516 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 7516 KB Output is correct
14 Correct 3 ms 7516 KB Output is correct
15 Correct 3 ms 7516 KB Output is correct
16 Correct 3 ms 7512 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 7348 KB Output is correct
20 Correct 4 ms 7516 KB Output is correct
21 Correct 3 ms 7512 KB Output is correct
22 Correct 3 ms 7516 KB Output is correct
23 Correct 3 ms 7512 KB Output is correct
24 Correct 3 ms 7460 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 3 ms 7516 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 43356 KB Output is correct
2 Correct 117 ms 24652 KB Output is correct
3 Correct 119 ms 25156 KB Output is correct
4 Correct 112 ms 23112 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 229 ms 39640 KB Output is correct
8 Correct 212 ms 39248 KB Output is correct
9 Correct 215 ms 39084 KB Output is correct
10 Correct 214 ms 39132 KB Output is correct
11 Correct 206 ms 43336 KB Output is correct
12 Correct 137 ms 30016 KB Output is correct
13 Correct 79 ms 23040 KB Output is correct
14 Correct 132 ms 30024 KB Output is correct
15 Correct 195 ms 36424 KB Output is correct
16 Correct 195 ms 38224 KB Output is correct
17 Correct 163 ms 34120 KB Output is correct
18 Correct 167 ms 33604 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 7772 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 274 ms 33408 KB Output is correct
2 Correct 198 ms 30964 KB Output is correct
3 Correct 218 ms 32752 KB Output is correct
4 Correct 82 ms 19280 KB Output is correct
5 Correct 302 ms 56584 KB Output is correct
6 Correct 295 ms 54084 KB Output is correct
7 Correct 302 ms 60580 KB Output is correct
8 Correct 318 ms 59060 KB Output is correct
9 Correct 285 ms 48328 KB Output is correct
10 Correct 290 ms 46724 KB Output is correct
11 Correct 318 ms 63488 KB Output is correct
12 Correct 140 ms 25208 KB Output is correct
13 Correct 295 ms 51892 KB Output is correct
14 Correct 289 ms 43852 KB Output is correct
15 Correct 269 ms 33484 KB Output is correct
16 Correct 220 ms 31532 KB Output is correct
17 Correct 190 ms 31260 KB Output is correct
18 Correct 227 ms 33108 KB Output is correct
19 Correct 130 ms 25252 KB Output is correct
20 Correct 64 ms 17748 KB Output is correct
21 Correct 208 ms 32848 KB Output is correct