Submission #763306

#TimeUsernameProblemLanguageResultExecution timeMemory
763306vjudge1Power Plant (JOI20_power)C++14
0 / 100
3 ms5076 KiB
#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)

power.cpp: In function 'void dfs(int, bool)':
power.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for (int i = 0; i < graph[node].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...