Problem: https://usaco.org/index.php?page=viewproblem2&cpid=1422
My code passed first 9 test cases and gives wrong answer on the rest. Even after looking at the reference solution (https://usaco.org/current/data/sol_prob1_silver_open24.html) I still cannot figure out why mine is wrong. Can anyone look at my code and give me some insight?
The idea is simple: I use a priority queue to simulate the process. At the same time, I use a disjoint data structure to union cows who finishes at the same time during the process. When two farmers finishes interview at the same time, I union them, and let any one of them interviews the next cow. The set of farmers that can interview the N+1’s cow are the cows that are in the same cluster as the cow on the top of the priority queue when finishing all N cows.
#include <bits/stdc++.h>
using namespace std;
#define int long long
class DisjointSet {
unordered_map<int, int> parent;
unordered_map<int, int> rank;
public:
void makeSet(vector<int> const &universe){
for (int i : universe){
parent[i] = i;
rank[i] = 0;
}
}
void makeSet(int element) {
parent[element] = element;
rank[element] = 0;
}
int Find(int k){
assert(parent.find(k) != parent.end());
if (parent[k] != k) parent[k] = Find(parent[k]);
return parent[k];
}
void Union(int a, int b) {
assert(parent.find(a) != parent.end() && parent.find(b) != parent.end());
int x = Find(a), y = Find(b);
//cout << "union rep " << x << ", " << y << endl;
if (x == y) return;
if (rank[x] > rank[y]) parent[y] = x;
else if (rank[x] < rank[y]) parent[x] = y;
else{
parent[x] = y;
rank[y]++;
}
}
};
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, k;
cin >> n >> k;
vector<int> cows(n);
DisjointSet ds;
for(int i = 0; i < n; ++ i) cin >> cows[i];
for(int i = 0; i < k; ++ i) ds.makeSet(i);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
for(int i = 0; i < k; ++ i) pq.push({cows[i], i});
for(int i = k; i < n; ++ i) {
int t = pq.top().first, idx = pq.top().second;
pq.pop();
if(pq.size() > 0 && pq.top().first == t){
// this cow finishes at the same time as cow idx, union them
ds.Union(idx, pq.top().second);
}
pq.push({t + cows[i], idx});
}
int t = pq.top().first, idx = pq.top().second;
pq.pop();
while(pq.size() > 0 && pq.top().first == t) {
ds.Union(idx, pq.top().second);
pq.pop();
}
string res = "";
for(int i = 0; i < k; ++ i) {
if(ds.Find(i) == ds.Find(idx)) res.push_back('1');
else res.push_back('0');
}
cout << t << endl;
cout << res << endl;
return 0;
}