QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#281569#3241. 最小公倍树wtcc#RE 0ms0kbC++14854b2023-12-10 13:07:142023-12-10 13:07:15

Judging History

This is the latest submission verdict.

  • [2023-12-10 13:07:15]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2023-12-10 13:07:14]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1000009;
ll a[N],L,R,p[N],m;
struct edge{
	ll u,v,w;
}edges[N];
ll fl(ll x){
	if(p[x]==x) return x;
	else return p[x]=fl(p[x]);
}
bool cmp(edge x,edge y){
	return x.w<y.w||x.w==y.w&&x.u<y.u;
}
int main(){
    cin>>L>>R;
    for(ll i=L;i<=R;i++) p[i]=i;
    for(ll i=1;i<=R;i++){
        ll f=ceil(1.0*L/i)*i;
        for(ll j=f+i;j<=R;j+=i){
            // cout<<f<<" "<<j<<endl;
		    edges[++m]=(edge){f,j,f*j/__gcd(f,j)};
        }
    }
    ll ans=0,chosen=0;
	sort(edges+1,edges+1+m,cmp);
	for(ll i=1;i<=m;i++){
		ll u=edges[i].u,v=edges[i].v,w=edges[i].w;
		if(fl(u)==fl(v)) continue;
		chosen++;
        // cout<<u<<" "<<v<<" "<<w<<endl;
		p[fl(u)]=fl(v);
		ans+=w;
		if(chosen==R-L) break;
	} 
    cout<<ans<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

100000 200000

output:


result: