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 <iostream>↵
#include <vector>↵
#include <unordered_set>↵
#include <queue>↵
using ll=long long;↵
using namespace std;↵
class DSU{↵
public:↵
vector<ll> a;↵
vector<ll> 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<ll> 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<ll>,greater<ll>> 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";↵
}↵
https://replit.com/@ethantherobot7/USACO-OPEN-2024-S1?v=1
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 <vector>↵
#include <unordered_set>↵
#include <queue>↵
using ll=long long;↵
using namespace std;↵
class DSU{↵
public:↵
vector<ll> a;↵
vector<ll> 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<ll> 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<ll>,greater<ll>> 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";↵
}↵
