hackercupai/hackercup
Data Preview The data available in this preview contains a 10 row dataset: Sample Dataset ("sample"): This is a subset of the full dataset, containing data from 2023. To view full dataset, download output_dataset.parquet. This contains data from 2011 to 2023. Fields The dataset include the following fields: name (string) year (string) round (string) statement (string) input (string) solution (string) code (string) sample_input (string) sample_output (string)… See the full description on the dataset page: https://huggingface.co/datasets/hackercupai/hackercup.
242.2k
1#include <algorithm>2#include <iostream>3#include <tuple>4#include <vector>5using namespace std;6 7using int64 = long long;8 9int N, M;10vector<int64> P;11vector<pair<int, int>> dsu_lists;12vector<int> dsu_par;13vector<int64> dsu_w, ans;14 15inline int get_parent(int x) {16 return x == dsu_par[x] ? x : (dsu_par[x] = get_parent(dsu_par[x]));17}18 19void unite(int x, int y) {20 if (P[x] < P[y]) {21 swap(x, y);22 }23 if (P[x] > dsu_w[y]) {24 for (int ind = y;;) {25 ans[ind] += max(0LL, P[x] - dsu_w[y] - ans[ind]);26 if (ind == dsu_lists[ind].first) {27 break;28 }29 ind = dsu_lists[ind].first;30 }31 }32 dsu_lists[dsu_lists[x].second].first = y;33 dsu_lists[x].second = dsu_lists[y].second;34 dsu_w[x] += dsu_w[y];35 dsu_par[y] = dsu_par[x];36}37 38int64 solve() {39 cin >> N >> M;40 P.resize(N);41 for (int i = 0; i < N; i++) {42 cin >> P[i];43 }44 vector<pair<int, int>> E(M);45 vector<tuple<int64, int64, int>> order;46 for (int i = 0; i < M; i++) {47 cin >> E[i].first >> E[i].second;48 if (P[--E[i].first] < P[--E[i].second]) {49 swap(E[i].first, E[i].second);50 }51 order.emplace_back(P[E[i].first], P[E[i].second], i);52 }53 sort(order.begin(), order.end());54 vector<pair<int, int>> E_buf(M);55 for (int i = 0; i < M; i++) {56 E_buf[i] = E[get<2>(order[i])];57 }58 E = E_buf;59 ans.assign(N, 0LL);60 dsu_lists.resize(N);61 dsu_w.assign(N, 0LL);62 dsu_par.resize(N);63 for (int i = 0; i < N; i++) {64 dsu_par[i] = i;65 dsu_w[i] = P[i];66 dsu_lists[i] = make_pair(i, i);67 }68 for (int i = 0; i < M; i++) {69 int x = get_parent(E[i].first);70 int y = get_parent(E[i].second);71 if (x == y) {72 continue;73 }74 unite(x, y);75 }76 int64 res = 0LL;77 for (int i = 0; i < N; i++) {78 res += ans[i];79 }80 return res;81}82 83int main() {84 ios_base::sync_with_stdio(false);85 cin.tie(0);86 int T;87 cin >> T;88 for (int t = 1; t <= T; t++) {89 cout << "Case #" << t << ": " << solve() << endl;90 }91 return 0;92}93