This is for USACO Silver Open problem 1 here: https://usaco.org/index.php?page=viewproblem2&cpid=1422 My code below doesn't seem to have a bug in it, and is mostly the same to the solution given, but it only passes the test cases with N <=3 * 10^3 but the server simply says wrong answer, and not timeout, and I can't see any obvious oversights. Thanks to anyone who looked at this. Code:

include

include

include

include

using ll=long long; using namespace std; class DSU{ public: vector a; vector size; DSU(ll n){ a.resize(n+1,0); size.resize(n+1,1); } void make_set(ll v){ a[v]=v; size[v]=1; } ll find_set(ll v){ if(a[v]==0)return 0; if(v==a[v])return v; return a[v]=find_set(a[v]); } void un_set(ll c,ll b){ c=find_set(c); b=find_set(b); if(c!=b){ if(size[c]<size[b]){ swap(c,b); } a[b]=c; size[c]+=size[b]; } } }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll n,k; cin >> n >> k; ll curT=0; deque q; ll a[k]; for(ll i=0;i<k;i++) a[i]=i+1; priority_queue<pair<ll,ll>,vector<pair<ll,ll>>, greater<pair<ll,ll>> > f; priority_queue<ll,vector,greater> aval(a,a+k);

for(ll i=0;i<n;i++){
    ll x;
    cin >> x;
    q.push_back(x);
}
DSU ds(n);
while(!q.empty()){
    if(f.size()<k){
        f.push(make_pair(curT+q.front(),aval.top()) );
        aval.pop();
        q.pop_front();
    }else{
        curT=f.top().first;

        aval.push(f.top().second);
        ll x=f.top().second;
        f.pop();
        while(!f.empty() && f.top().first==curT){
            if(ds.find_set(x)==0)ds.make_set(x);
            ll nx=f.top().second;
            if(ds.find_set(nx)==0)ds.make_set(nx);
            ds.un_set(x,nx);
            aval.push(f.top().second);
            f.pop();
        }
    }
}
if(f.size()==k){
    curT=f.top().first;
    aval.push(f.top().second);
    ll x=f.top().second;
    f.pop();
    while(!f.empty() && f.top().first==curT){
        if(ds.find_set(x)==0)ds.make_set(x);
        ll nx=f.top().second;
        if(ds.find_set(nx)==0)ds.make_set(nx);
        ds.un_set(x,nx);
        aval.push(f.top().second);
        f.pop();
    }
}

unordered_set<ll> goodPars;
while(!aval.empty()){
    goodPars.emplace(ds.find_set(aval.top()));
    aval.pop();
}
cout << curT << "\n";
string ans;
for(ll i=1;i<=k;i++){
    if(goodPars.find(ds.find_set(i))!=goodPars.end()){
        ans+='1';
    }else{
        ans+='0';
    }
}
cout << ans << "\n";

}