QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#259926 | #7749. A Simple MST Problem | ucup-team1508 | WA | 303ms | 148416kb | C++20 | 3.3kb | 2023-11-21 16:17:04 | 2023-11-21 16:17:05 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N = 1e6 + 10;
const int inf = 1e18;
typedef array<int, 3> a3;
int L, R, l[N], r[N], p[N], pr[N], idx = 0, is_prime[N], dis[N], vst[N], cnt[N], fa[N];
int mp1[N], mp2[N];
vector<pii> ed[N];
vector<int> a[N];
vector<a3> q;
int st;
int find(int x) {return x == fa[x] ? x : find(fa[x]);}
bool merge(int x, int y) {
int p = find(x), q = find(y);
if(p == q) return false;
fa[p] = q;
return true;
}
void init() {
int MAX = 1e6;
p[1] = 1;
F(i, 2, MAX) {
if(! p[i]) pr[++ idx] = i, p[i] = i, is_prime[i] = 1, a[i].pb(i);
for(int j = 1; j <= idx && pr[j] * i <= MAX; j ++) {
p[i * pr[j]] = pr[j];
a[i * pr[j]] = a[i];
if(p[i] == pr[j]) break;
else a[i * pr[j]].pb(pr[j]);
}
}
F(i, 1, MAX) {
l[i] = 0;
int sz = a[i].size();
F(j, 0, (1 << sz) - 1) {
int tmp = 1;
F(k, 0, sz - 1) if((j >> k) & 1) tmp *= a[i][k];
l[i] = max(l[i], mp1[tmp]);
}
int now = 1;
for(auto x : a[i]) now *= x;
mp1[now] = i;
}
F(i, 1, MAX) mp2[i] = MAX + 1;
Fd(i, MAX, 1) {
r[i] = MAX + 1;
int sz = a[i].size();
F(j, 0, (1 << sz) - 1) {
int tmp = 1;
F(k, 0, sz - 1) if((j >> k) & 1) tmp *= a[i][k];
r[i] = min(r[i], mp2[tmp]);
}
int now = 1;
for(auto x : a[i]) now *= x;
mp2[now] = i;
}
}
int prim(int l, int r) {
int res = 0;
F(i, l, r) dis[i] = inf, vst[i] = 0, ed[i].clear();
dis[l] = 0;
F(i, l, r) F(j, i + 1, r) {
int w = 0;
for(auto x : a[i]) w += ! cnt[x] ++;
for(auto x : a[j]) w += ! cnt[x] ++;
for(auto x : a[i]) cnt[x] --;
for(auto x : a[j]) cnt[x] --;
ed[i].pb({j, w}), ed[j].pb({i, w});
}
F(i, l, r) {
int u = 0, now = inf;
F(j, l, r) if(! vst[j] && dis[j] < now) u = j, now = dis[j];
vst[u] = 1, res += now;
for(auto [v, w] : ed[u]) dis[v] = min(dis[v], w);
}
return res;
}
void sol() {
cin >> L >> R;
int flag = 0;
F(i, L, R) if(is_prime[i]) flag = i;
if(! flag) {
cout << prim(L, R) << "\n";
return;
}
q.clear();
F(i, L, R) {
if(l[i] >= L) q.pb({(int)a[i].size(), i, l[i]});
if(r[i] <= R) q.pb({(int)a[i].size(), i, r[i]});
int w = a[i].size() + 1;
if(is_prime[i]) {
F(j, L, R) if(j != i) {
q.pb({w, i, j});
break;
}
} else q.pb({w, i, flag});
}
F(i, L, R) fa[i] = i;
int res = 0, tot = 0;
sort(q.begin(), q.end());
for(auto [w, u, v] : q) {
if(! merge(u, v)) continue;
res += w;
if(++ tot == R - L) break;
}
cout << res << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
init();
int t; cin >> t;
F(i, 1, t) sol();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 199ms
memory: 147144kb
input:
5 1 1 4 5 1 4 1 9 19 810
output:
0 2 3 9 1812
result:
ok 5 lines
Test #2:
score: -100
Wrong Answer
time: 303ms
memory: 148416kb
input:
2 27 30 183704 252609
output:
8 223091
result:
wrong answer 2nd lines differ - expected: '223092', found: '223091'