Submission #1092422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092422		MinhTuan11	Firefighting (NOI20_firefighting)	C++17	74 / 100	299 ms	69272 KiB

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) {
	// 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(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.size() == 0) return;
			if(a.back() + mini > mid) {
				// cout << "+ " << u << '\n';
				pos.push_back(u);
				cnt++;
				return;
			}
		}
		return;
	}
	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(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 (stderr)

Firefighting.cpp: In function 'int main()':
Firefighting.cpp:195:10: warning: unused variable 'pcnt' [-Wunused-variable]
  195 |      int pcnt = cnt;
      |          ^~~~
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.inp", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Firefighting.cpp:178:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |      freopen("file.out", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 19 / 19
• Subtask 5: 0 / 26
• Subtask 6: 38 / 38