oj.uz

답안 #1091245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1091245 2024-09-20T08:35:15 Z MinhTuan11 Firefighting (NOI20_firefighting) C++17
3 / 100
 243 ms 54600 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);
		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() > mid && 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] = -h[u];
		}
	}
}

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

# 결과 실행 시간 메모리 Grader output
1 Correct 228 ms 41660 KB Output is correct
2 Correct 225 ms 41656 KB Output is correct
3 Correct 61 ms 20168 KB Output is correct
4 Correct 226 ms 40868 KB Output is correct
5 Correct 4 ms 7512 KB Output is correct
6 Correct 5 ms 7516 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7516 KB Output is correct
4 Incorrect 3 ms 7516 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 4 ms 7516 KB Output is correct
3 Correct 4 ms 7516 KB Output is correct
4 Correct 4 ms 7512 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 4 ms 7512 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 4 ms 7516 KB Output is correct
9 Correct 5 ms 7516 KB Output is correct
10 Correct 3 ms 7516 KB Output is correct
11 Incorrect 3 ms 7512 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 222 ms 41632 KB Output is correct
2 Correct 92 ms 24344 KB Output is correct
3 Incorrect 104 ms 24868 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 7772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 36432 KB Output is correct
2 Correct 188 ms 34920 KB Output is correct
3 Correct 175 ms 37204 KB Output is correct
4 Correct 66 ms 21256 KB Output is correct
5 Correct 241 ms 54600 KB Output is correct
6 Incorrect 243 ms 52040 KB Output isn't correct
7 Halted 0 ms 0 KB -