oj.uz

Submission #1091259

# Submission time Handle Problem Language Result Execution time Memory
1091259 2024-09-20T09:47:11 Z MinhTuan11 Firefighting (NOI20_firefighting) C++17
55 / 100
 324 ms 63492 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] = inf;
			b[u] = -h[u];
		}
		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 276 ms 43580 KB Output is correct
2 Correct 285 ms 43572 KB Output is correct
3 Correct 74 ms 20040 KB Output is correct
4 Correct 262 ms 42820 KB Output is correct
5 Correct 4 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 3 ms 7768 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 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 3 ms 7516 KB Output is correct
11 Correct 3 ms 7516 KB Output is correct
12 Correct 4 ms 7512 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

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 4 ms 7512 KB Output is correct
4 Correct 3 ms 7364 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 7512 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 3 ms 7516 KB Output is correct
12 Correct 3 ms 7400 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 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 7516 KB Output is correct
21 Correct 4 ms 7516 KB Output is correct
22 Correct 3 ms 7516 KB Output is correct
23 Correct 3 ms 7296 KB Output is correct
24 Correct 3 ms 7516 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 4 ms 7516 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 43580 KB Output is correct
2 Correct 116 ms 24648 KB Output is correct
3 Correct 123 ms 25084 KB Output is correct
4 Correct 114 ms 23076 KB Output is correct
5 Correct 3 ms 7512 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 213 ms 39688 KB Output is correct
8 Correct 263 ms 39344 KB Output is correct
9 Correct 228 ms 39092 KB Output is correct
10 Correct 226 ms 39096 KB Output is correct
11 Correct 272 ms 43700 KB Output is correct
12 Runtime error 166 ms 49052 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 9 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 264 ms 33344 KB Output is correct
2 Correct 203 ms 30800 KB Output is correct
3 Correct 214 ms 32596 KB Output is correct
4 Correct 88 ms 19332 KB Output is correct
5 Correct 308 ms 56584 KB Output is correct
6 Correct 324 ms 54084 KB Output is correct
7 Correct 312 ms 60592 KB Output is correct
8 Correct 313 ms 59060 KB Output is correct
9 Correct 313 ms 48324 KB Output is correct
10 Correct 283 ms 46652 KB Output is correct
11 Correct 299 ms 63492 KB Output is correct
12 Correct 150 ms 25096 KB Output is correct
13 Correct 316 ms 51956 KB Output is correct
14 Correct 282 ms 43796 KB Output is correct
15 Correct 233 ms 33736 KB Output is correct
16 Correct 205 ms 31572 KB Output is correct
17 Correct 191 ms 31320 KB Output is correct
18 Correct 248 ms 33032 KB Output is correct
19 Correct 132 ms 25164 KB Output is correct
20 Correct 69 ms 17652 KB Output is correct
21 Correct 228 ms 32852 KB Output is correct