oj.uz

Submission #758360

# Submission time Handle Problem Language Result Execution time Memory
758360 2023-06-14T13:55:06 Z thimote75 Toll (APIO13_toll) C++14
16 / 100
 3 ms 304 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
using ipair = pair<int, int>;
using itrip = pair<int, pair<int, int>>;

using t_road  = itrip;
using t_roads = vector<t_road>;
using t_graph = vector<vector<itrip>>;

using idata = vector<int>;

template<typename T>
using lpq = priority_queue<T, vector<T>, less<T>>;

const int INF = 1e9;

int N, M, K;

t_graph roads;
idata critical_path;

const int GREEDY   = 0;
const int NORMAL   = 1;
const int DISABLED = 2;

struct Road {
    int cost, type;
    int a, b;

    Road (int cost, int type, int a, int b) : a(a), b(b), cost(cost), type(type) {}
};

using t_road_array = vector<Road*>;

bool operator_road (const Road* a, const Road* b) {
    if (a->cost != b->cost) return a->cost < b->cost;

    return a->type < b->type;
}

struct UFD {
private:
    idata data;
public:
    UFD (int size) {
        data.resize(size);

        for (int i = 0; i < size; i ++) data[i] = i;
    }

    int boss (int x) {
        if (data[x] != x)
            data[x]  = boss(data[x]);
    
        return data[x];
    }
    bool merge (int a, int b) {
        a = boss(a); b = boss(b);

        data[a] = b;

        return a != b;
    }
};

t_road_array filter_mst ( t_road_array &roads ) {
    sort(roads.begin(), roads.end(), operator_road);

    UFD ufd(N);

    t_road_array result;

    for (const auto &road : roads) {
        if (road->type == DISABLED) continue ;
        if (!ufd.merge(road->a, road->b)) continue ;

        result.push_back(road);
    }

    return result;
}
int max_on_path (int node, int parent, int target) {
    if (node == target) return 0;

    for (const auto &road : roads[node]) if (road.first != parent) {
        int next = max_on_path(road.first, node, target);
        if (next == -1) continue ;

        return max(next, road.second.first);
    }

    return -1;
}

idata people_count;

// returns { people_count, tax_gained }
pair<int, int> result_dfs (int node, int parent) {
    pair<int, int> result = { people_count[node], 0 };

    for (t_road road : roads[node]) if (road.first != parent) {
        pair<int, int> local = result_dfs(road.first, node);

        result.first  += local.first;
        result.second += local.second;

        if (road.second.second == NORMAL) continue ;

        result.second += road.second.first * local.first;
    }

    return result;
}
int compute (t_road_array road_array) {
    t_road_array filtered = filter_mst(road_array);

    for (int i = 0; i < N; i ++)
        roads[i].clear();
    
    for (Road* road : filtered) {
        roads[road->a].push_back({ road->b, { road->cost, road->type } });
        roads[road->b].push_back({ road->a, { road->cost, road->type } });
    }

    return result_dfs(0, -1).second;
}

signed main () {
    cin >> N >> M >> K;

    roads.resize(N);

    t_road_array road_array;

    for (int i = 0; i < M; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        a --;
        b --;

        road_array.push_back(new Road(c, NORMAL, a, b));
    }

    t_road_array filtered_mst = filter_mst(road_array);

    for (Road* road : filtered_mst) {
        roads[road->a].push_back({ road->b, { road->cost, road->type } });
        roads[road->b].push_back({ road->a, { road->cost, road->type } });
    }

    t_road_array k_roads;
    for (int iR = 0; iR < K; iR ++) {
        int a, b;
        cin >> a >> b;
        a --; b --;

        int cost = max_on_path(a, -1, b);

        Road* road = new Road(cost, DISABLED, a, b);

        k_roads     .push_back(road);
        filtered_mst.push_back(road);
    }

    people_count.resize(N);
    for (int i = 0; i < N; i ++)
        cin >> people_count[i];

    int max_value = 0;

    for (int mask = 0; mask < (1 << K); mask ++) {
        for (int iK = 0; iK < K; iK ++) {
            if ((1 << iK) & mask) k_roads[iK]->type = GREEDY;
            else k_roads[iK]->type = DISABLED;
        }

        max_value = max(max_value, compute(filtered_mst));
    }

    cout << max_value << endl;
}

Compilation message

toll.cpp: In constructor 'Road::Road(long long int, long long int, long long int, long long int)':
toll.cpp:32:12: warning: 'Road::b' will be initialized after [-Wreorder]
   32 |     int a, b;
      |            ^
toll.cpp:31:9: warning:   'long long int Road::cost' [-Wreorder]
   31 |     int cost, type;
      |         ^~~~
toll.cpp:34:5: warning:   when initialized here [-Wreorder]
   34 |     Road (int cost, int type, int a, int b) : a(a), b(b), cost(cost), type(type) {}
      |     ^~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 3 ms 304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 3 ms 304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 3 ms 304 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 3 ms 304 KB Output isn't correct
4 Halted 0 ms 0 KB -