# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
763306 | vjudge1 | Power Plant (JOI20_power) | C++14 | 3 ms | 5076 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_N = 100000;
vector<int> graph[MAX_N]; // Đồ thị lưu kết nối giữa các căn cứ
bool hasGenerator[MAX_N]; // Mảng lưu trạng thái có máy phát điện hay không
bool visited[MAX_N]; // Mảng lưu trạng thái đã thăm của các căn cứ
int profit = 0; // Biến lưu tổng lợi nhuận
// Hàm DFS để duyệt đồ thị và tính lợi nhuận tối đa
void dfs(int node, bool isBroken) {
visited[node] = true;
// Nếu căn cứ hiện tại có máy phát điện và không hỏng
if (hasGenerator[node] && !isBroken) {
profit++;
isBroken = true; // Đánh dấu máy phát điện bị hỏng
}
// Duyệt qua tất cả các căn cứ kề với căn cứ hiện tại
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i];
if (!visited[neighbor]) {
dfs(neighbor, isBroken);
}
}
}
int main() {
int N;
cin >> N; // Nhập số lượng căn cứ
// Đọc thông tin về máy phát điện của từng căn cứ
for (int i = 0; i < N; i++) {
int generator;
cin >> generator;
hasGenerator[i + 1] = (generator == 1); // 1: có máy phát điện, 0: không có máy phát điện
}
// Đọc thông tin về kết nối giữa các căn cứ
for (int i = 0; i < N - 1; i++) {
int base1, base2;
cin >> base1 >> base2;
graph[base1].push_back(base2);
graph[base2].push_back(base1);
}
// Duyệt qua từng căn cứ để tính lợi nhuận tối đa
for (int i = 1; i <= N; i++) {
memset(visited, false, sizeof(visited)); // Reset mảng visited trước mỗi lần duyệt
dfs(i, false);
}
// Tính tổng lợi nhuận
int totalProfit = profit - (N - profit);
cout << totalProfit << endl;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |