QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #617898 | #7749. A Simple MST Problem | MIS_T__ | Compile Error | / | / | C++23 | 5.3kb | 2024-10-06 17:34:50 | 2024-10-06 17:34:52 |
Judging History
answer
#include <bits/stdc++.h>#include <bits/stdc++.h>#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using i64 = long long;
const int N = 1e6 + 5;
int sum[N];
int num[N];
vector<int>isp(N,1);
vector<int>bas(N,1);
vector<int>sz(N),vis(N);
vector<int>u[N];
int check(int x,int y) {
return num[x]+num[y]-num[__gcd(x,y)];
}
void Euler_prime(int n){
isp[0] = 0;
isp[1] = 0;
for ( int i = 2 ; i <= n ; i++ ) {
if ( !isp[i] ) continue;
for ( int j = 1; i*j <= n ; j++ ) {
num[i*j]++;
bas[i*j] *= i;
if ( j != 1 ) isp[i*j] = 0;
u[i*j].emplace_back(i);
}
}
for ( int i = 1 ; i <= n ; i++ ) {
sum[i] += sum[i-1]+isp[i];
}
}
void solve() {
int l,r;
cin >> l >> r;
if ( l == 1 ) {
int res = 0;
for ( int i = 2 ; i <= r ; i++ ) {
res += num[i];
}
cout << res << '\n';
return;
}
int t = sum[r]-sum[l-1];
i64 ans = 0;
if ( t ) {
for (int i=1;i<=r;++i) sz[i]=vis[i]=0;
for (int i=l;i<=r;++i) ++sz[bas[i]];
for (int i=2;i<=r;++i) if (!vis[i]&&sz[i])
{
ans+=num[i]*(sz[i]-1)+(num[i]+1); vis[i]=1;
for (int j=i*2;j<=r;j+=i) if (!vis[j]&&sz[j])
vis[j]=1,ans+=num[j]*sz[j];
}
ans -= 2;
} else {
int n = r-l+1;
vector<int>dis(n,1e9);
dis[0] = 0;
int idx = 0;
vector<int>f(n,0);
for ( int i = 1 ; i < n ; i++ ) {
int mx = 1e9;
int id = 0;
f[idx] = 1;
for ( int j = 0 ; j < n ; j++ ) {
if ( f[j] ) continue;
dis[j] = min(dis[j],dis[idx]+check(idx+l,j+l));
if ( dis[j] < mx ) {
mx = dis[j];
id = j;
}
}
ans += dis[id];
dis[id] = 0;
idx = id;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
Euler_prime(1000000);
int T = 1;
cin >> T;
while ( T-- ) {
solve();
}
}
// 1 2 3
// 1 2 3
// 1 2 3
using namespace std;
using ull = unsigned long long;
using i64 = long long;
const int N = 1e6 + 5;
int sum[N];
int num[N];
vector<int>isp(N,1);
vector<int>bas(N,1);
vector<int>sz(N),vis(N);
vector<int>u[N];
int check(int x,int y) {
return num[x]+num[y]-num[__gcd(x,y)];
}
void Euler_prime(int n){
isp[0] = 0;
isp[1] = 0;
for ( int i = 2 ; i <= n ; i++ ) {
if ( !isp[i] ) continue;
for ( int j = 1; i*j <= n ; j++ ) {
num[i*j]++;
bas[i*j] *= i;
if ( j != 1 ) isp[i*j] = 0;
u[i*j].emplace_back(i);
}
}
for ( int i = 1 ; i <= n ; i++ ) {
sum[i] += sum[i-1]+isp[i];
}
}
void solve() {
int l,r;
cin >> l >> r;
if ( l == 1 ) {
int res = 0;
for ( int i = 2 ; i <= r ; i++ ) {
res += num[i];
}
cout << res << '\n';
return;
}
int t = sum[r]-sum[l-1];
i64 ans = 0;
if ( t ) {
for (int i=1;i<=r;++i) sz[i]=vis[i]=0;
for (int i=l;i<=r;++i) ++sz[bas[i]];
for (int i=2;i<=r;++i) if (!vis[i]&&sz[i])
{
ans+=num[i]*(sz[i]-1)+(num[i]+1); vis[i]=1;
for (int j=i*2;j<=r;j+=i) if (!vis[j]&&sz[j])
vis[j]=1,ans+=num[j]*sz[j];
}
ans -= 2;
} else {
int n = r-l+1;
vector<int>dis(n,1e9);
dis[0] = 0;
int idx = 0;
vector<int>f(n,0);
for ( int i = 1 ; i < n ; i++ ) {
int mx = 1e9;
int id = 0;
f[idx] = 1;
for ( int j = 0 ; j < n ; j++ ) {
if ( f[j] ) continue;
dis[j] = min(dis[j],dis[idx]+check(idx+l,j+l));
if ( dis[j] < mx ) {
mx = dis[j];
id = j;
}
}
ans += dis[id];
dis[id] = 0;
idx = id;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
Euler_prime(1000000);
int T = 1;
cin >> T;
while ( T-- ) {
solve();
}
}
// 1 2 3
// 1 2 3
// 1 2 3
using namespace std;
using ull = unsigned long long;
using i64 = long long;
const int N = 1e6 + 5;
int sum[N];
int num[N];
vector<int>isp(N,1);
vector<int>bas(N,1);
int check(int x,int y) {
return num[x]+num[y]-num[__gcd(x,y)];
}
void Euler_prime(int n){
isp[0] = 0;
isp[1] = 0;
for ( int i = 2 ; i <= n ; i++ ) {
if ( !isp[i] ) continue;
for ( int j = 1; i*j <= n ; j++ ) {
num[i*j]++;
if ( j != 1 ) isp[i*j] = 0;
bas[i*j] *= i;
}
}
for ( int i = 1 ; i <= n ; i++ ) {
sum[i] += sum[i-1]+isp[i];
}
}
void solve() {
int l,r;
cin >> l >> r;
if ( l == 1 ) {
int res = 0;
for ( int i = 2 ; i <= r ; i++ ) {
res += num[i];
}
cout << res << '\n';
return;
}
int t = sum[r]-sum[l-1];
i64 ans = 0;
if ( t ) {
vector<int>vis(r+1,1);
map<int,int>mp;
for ( int i = l ; i <= r ; i++ ) {
mp[bas[i]]++;
}
int cnt = 0;
for ( auto [i,k] : mp ) {
for ( int j = 2 ; i*j <= 1000000 ; j++ ) {
if ( mp.contains(i*j) ) {
ans += num[i*j]*mp[i*j];
mp.erase(i*j);
}
}
ans += k*num[i];
cnt++;
}
ans += cnt-2;
} else {
int n = r-l+1;
vector<int>dis(n,1e9);
dis[0] = 0;
int idx = 0;
vector<int>f(n,0);
for ( int i = 1 ; i < n ; i++ ) {
int mx = 1e9;
int id = 0;
f[idx] = 1;
for ( int j = 0 ; j < n ; j++ ) {
if ( f[j] ) continue;
dis[j] = min(dis[j],dis[idx]+check(idx+l,j+l));
if ( dis[j] < mx ) {
mx = dis[j];
id = j;
}
}
ans += dis[id];
dis[id] = 0;
idx = id;
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
Euler_prime(1000000);
int T = 1;
cin >> T;
while ( T-- ) {
solve();
}
}
// 1 2 3
// 1 2 3
// 1 2 3
Details
answer.code:1:25: warning: extra tokens at end of #include directive
1 | #include <bits/stdc++.h>#include <bits/stdc++.h>#include <bits/stdc++.h>
| ^
answer.code:97:11: error: redefinition of ‘const int N’
97 | const int N = 1e6 + 5;
| ^
answer.code:5:11: note: ‘const int N’ previously defined here
5 | const int N = 1e6 + 5;
| ^
answer.code:98:5: error: redefinition of ‘int sum [1000005]’
98 | int sum[N];
| ^~~
answer.code:6:5: note: ‘int sum [1000005]’ previously declared here
6 | int sum[N];
| ^~~
answer.code:99:5: error: redefinition of ‘int num [1000005]’
99 | int num[N];
| ^~~
answer.code:7:5: note: ‘int num [1000005]’ previously declared here
7 | int num[N];
| ^~~
answer.code:100:12: error: redefinition of ‘std::vector<int> isp’
100 | vector<int>isp(N,1);
| ^~~
answer.code:8:12: note: ‘std::vector<int> isp’ previously declared here
8 | vector<int>isp(N,1);
| ^~~
answer.code:101:12: error: redefinition of ‘std::vector<int> bas’
101 | vector<int>bas(N,1);
| ^~~
answer.code:9:12: note: ‘std::vector<int> bas’ previously declared here
9 | vector<int>bas(N,1);
| ^~~
answer.code:102:12: error: redefinition of ‘std::vector<int> sz’
102 | vector<int>sz(N),vis(N);
| ^~
answer.code:10:12: note: ‘std::vector<int> sz’ previously declared here
10 | vector<int>sz(N),vis(N);
| ^~
answer.code:102:18: error: redefinition of ‘std::vector<int> vis’
102 | vector<int>sz(N),vis(N);
| ^~~
answer.code:10:18: note: ‘std::vector<int> vis’ previously declared here
10 | vector<int>sz(N),vis(N);
| ^~~
answer.code:103:12: error: redefinition of ‘std::vector<int> u [1000005]’
103 | vector<int>u[N];
| ^
answer.code:11:12: note: ‘std::vector<int> u [1000005]’ previously defined here
11 | vector<int>u[N];
| ^
answer.code:104:5: error: redefinition of ‘int check(int, int)’
104 | int check(int x,int y) {
| ^~~~~
answer.code:12:5: note: ‘int check(int, int)’ previously defined here
12 | int check(int x,int y) {
| ^~~~~
answer.code:107:6: error: redefinition of ‘void Euler_prime(int)’
107 | void Euler_prime(int n){
| ^~~~~~~~~~~
answer.code:15:6: note: ‘void Euler_prime(int)’ previously defined here
15 | void Euler_prime(int n){
| ^~~~~~~~~~~
answer.code:123:6: error: redefinition of ‘void solve()’
123 | void solve() {
| ^~~~~
answer.code:31:6: note: ‘void solve()’ previously defined here
31 | void solve() {
| ^~~~~
answer.code:171:5: error: redefinition of ‘int main()’
171 | int main() {
| ^~~~
answer.code:79:5: note: ‘int main()’ previously defined here
79 | int main() {
| ^~~~
answer.code:189:11: error: redefinition of ‘const int N’
189 | const int N = 1e6 + 5;
| ^
answer.code:5:11: note: ‘const int N’ previously defined here
5 | const int N = 1e6 + 5;
| ^
answer.code:190:5: error: redefinition of ‘int sum [1000005]’
190 | int sum[N];
| ^~~
answer.code:6:5: note: ‘int sum [1000005]’ previously declared here
6 | int sum[N];
| ^~~
answer.code:191:5: error: redefinition of ‘int num [1000005]’
191 | int num[N];
| ^~~
answer.code:7:5: note: ‘int num [1000005]’ previously declared here
7 | int num[N];
| ^~~
answer.code:192:12: error: redefinition of ‘std::vector<int> isp’
192 | vector<int>isp(N,1);
| ^~~
answer.code:8:12: note: ‘std::vector<int> isp’ previously declared here
8 | vector<int>isp(N,1);
| ^~~
answer.code:193:12: error: redefinition of ‘std::vector<int> bas’
193 | vector<int>bas(N,1);
| ^~~
answer.code:9:12: note: ‘std::vector<int> bas’ previously declared here
9 | vector<int>bas(N,1);
| ^~~
answer.code:194:5: error: redefinition of ‘int check(int, int)’
194 | int check(int x,int y) {
| ^~~~~
answer.code:12:5: note: ‘int check(int, int)’ previously defined here
12 | int check(int x,int y) {
| ^~~~~
answer.code:197:6: error: redefinition of ‘void Euler_prime(int)’
197 | void Euler_prime(int n){
| ^~~~~~~~~~~
answer.code:15:6: note: ‘void Euler_prime(int)’ previously defined here
15 | void Euler_prime(int n){
| ^~~~~~~~~~~
answer.code:212:6: error: redefinition of ‘void solve()’
212 | void solve() {
| ^~~~~
answer.code:31:6: note: ‘void solve()’ previously defined here
31 | void solve() {
| ^~~~~
answer.code:268:5: error: redefinition of ‘int main()’
268 | int main() {
| ^~~~
answer.code:79:5: note: ‘int main()’ previously defined here
79 | int main() {
| ^~~~