oj.uz

Submission #968245

# Submission time Handle Problem Language Result Execution time Memory
968245 2024-04-23T08:44:14 Z ShauryaTheShep Toll (APIO13_toll) C++14
0 / 100
 101 ms 163840 KB 
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v;
    long long cost;
    bool operator<(const Edge& e) const {
        return cost < e.cost;
    }
};

int find(vector<int>& parent, int i) {
    if (parent[i] != i) {
        parent[i] = find(parent, parent[i]);
    }
    return parent[i];
}

void union_set(vector<int>& parent, vector<int>& rank, int a, int b) {
    a = find(parent, a);
    b = find(parent, b);
    if (a != b) {
        if (rank[a] < rank[b]) swap(a, b);
        parent[b] = a;
        if (rank[a] == rank[b]) rank[a]++;
    }
}

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<Edge> edges(M);
    for (int i = 0; i < M; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].cost;
    }

    int x, y;
    cin >> x >> y; // Only one new road for K=1

    vector<int> p(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> p[i];
    }

    sort(edges.begin(), edges.end());

    vector<int> parent(N + 1), rank(N + 1, 0);
    iota(parent.begin(), parent.end(), 0);

    long long max_revenue = 0;

    // Compute participants moving through each road to town 1
    vector<int> participants_through(N + 1, 0);
    function<void(int, int)> dfs = [&](int u, int prev) {
        participants_through[u] = p[u];
        for (const auto& e : edges) {
            if (e.u == u && e.v != prev) {
                dfs(e.v, u);
                participants_through[u] += participants_through[e.v];
            } else if (e.v == u && e.u != prev) {
                dfs(e.u, u);
                participants_through[u] += participants_through[e.u];
            }
        }
    };
    dfs(1, -1);

    // Trying different tolls for the new road
    for (long long toll = 1; toll <= 1000000; toll++) {
        vector<Edge> new_edges = edges;
        new_edges.push_back({x, y, toll});

        sort(new_edges.begin(), new_edges.end());
        iota(parent.begin(), parent.end(), 0);
        fill(rank.begin(), rank.end(), 0);

        long long mst_cost = 0, revenue = 0;
        int count = 0;

        for (const auto& e : new_edges) {
            if (find(parent, e.u) != find(parent, e.v)) {
                union_set(parent, rank, e.u, e.v);
                mst_cost += e.cost;
                if ((e.u == x && e.v == y) || (e.u == y && e.v == x)) {
                    revenue = toll * (participants_through[x] + participants_through[y]); // Assuming x and y are connected directly to town 1
                }
                if (++count == N - 1) break;
            }
        }

        max_revenue = max(max_revenue, revenue);
    }

    cout << max_revenue << endl;

    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 163840 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 163840 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 163840 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 163840 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 163840 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -