Submission #1055414

# Submission time Handle Problem Language Result Execution time Memory
1055414 2024-08-12T18:59:36 Z Hazard Closing Time (IOI23_closing) C++17
Compilation error
0 ms 0 KB
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_N = 100005;
const int MAX_M = 200005;

vector<int> graph[MAX_N];
int U[MAX_M], V[MAX_M], W[MAX_M];
int N, M, K, X, Y;

int dfs(int node, int time, int parent, vector<int>& closing_times) {
    int reachable = 0;
    for (int i = 0; i < graph[node].size(); i++) {
        int next_node = graph[node][i];
        if (next_node == parent) continue;
        int next_time = time + W[graph[node][i]];
        if (next_time <= closing_times[next_node]) {
            reachable += dfs(next_node, next_time, node, closing_times);
        }
    }
    return reachable + 1;
}

int compute_convenience_score(vector<int>& closing_times) {
    int score = 0;
    score += dfs(X, 0, -1, closing_times);
    score += dfs(Y, 0, -1, closing_times);
    return score;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> K >> X >> Y;
    for (int i = 0; i < M; i++) {
        cin >> U[i] >> V[i] >> W[i];
        graph[U[i]].push_back(i);
        graph[V[i]].push_back(i);
    }

    int max_score = 0;
    for (int mask = 0; mask < (1 << N); mask++) {
        vector<int> closing_times(N);
        for (int i = 0; i < N; i++) {
            closing_times[i] = (mask >> i) & 1;
        }
        int sum_closing_times = 0;
        for (int i = 0; i < N; i++) {
            sum_closing_times += closing_times[i];
        }
        if (sum_closing_times <= K) {
            int score = compute_convenience_score(closing_times);
            max_score = max(max_score, score);
        }
    }

    cout << max_score << endl;

    return 0;
}

Compilation message

closing.cpp: In function 'int dfs(int, int, int, std::vector<int>&)':
closing.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < graph[node].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc3Mmsov.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccF2S4Pu.o:closing.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc3Mmsov.o: in function `main':
grader.cpp:(.text.startup+0x6a1): undefined reference to `max_score(int, int, int, long long, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status