Submission #1091241

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091241	2024-09-20T08:23:56 Z	MinhTuan11	Firefighting (NOI20_firefighting)	C++17	3 / 100	241 ms	41812 KB

Firefighting

#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);
		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;
			}
		}
	}
	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] = 0;
		}
	}
}

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);
    }
    cout << cnt << '\n';
    for(int x : pos) cout << x << ' ';
    
    return 0;
}

// tuntun

Compilation message

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

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	210 ms	41812 KB	Output is correct
2	Correct	241 ms	41656 KB	Output is correct
3	Correct	64 ms	20164 KB	Output is correct
4	Correct	206 ms	40876 KB	Output is correct
5	Correct	3 ms	7512 KB	Output is correct
6	Correct	3 ms	7512 KB	Output is correct

Subtask #2
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	7516 KB	Output is correct
4	Correct	3 ms	7516 KB	Output is correct
5	Incorrect	3 ms	7516 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7520 KB	Output is correct
2	Correct	5 ms	7516 KB	Output is correct
3	Correct	4 ms	7524 KB	Output is correct
4	Correct	4 ms	7512 KB	Output is correct
5	Correct	4 ms	7516 KB	Output is correct
6	Correct	3 ms	7512 KB	Output is correct
7	Correct	5 ms	7512 KB	Output is correct
8	Correct	4 ms	7516 KB	Output is correct
9	Correct	3 ms	7516 KB	Output is correct
10	Incorrect	3 ms	7516 KB	Output isn't correct
11	Halted	0 ms	0 KB	-