QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267878#7749. A Simple MST ProblemmanizareCompile Error//C++143.8kb2023-11-27 20:13:142023-11-27 20:13:15

Judging History

你现在查看的是最新测评结果

  • [2023-11-27 20:13:15]
  • 评测
查看
  • [2023-11-27 20:13:14]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
vector <int> di[maxn] , vec[maxn] ; 
vector <pii> ed[maxn] ;

int find(int v){
	if(par[v]==0)return v; 
	return par[v] = find(par[v]);
}

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
	for(int i = 1; i <= N ; i++)a[i] = 1;
	for(int i = 2; i <= N ; i++){
		if(mark[i] == 1)continue ;
		for(int j = i ; j <= N ; j+=i){
			mark[j] = 1 ;
			a[j] *= i ;
			t[j]++;
		}
	}
	for(int i = 1; i <= N ; i++){
		if(a[i] != i)continue ;
		for(int j = i ; j <= N ; j+=i){
			if(a[j] == j)di[j].pb(i) ;
		}
	}
	int T ;cin >> T ;
	for(int i = 1; i <= T ; i++){
		for(int i =0 ; i <= 30 ; i++){
			ed[i].clear() ;
		}
		int l  ,r ;
		cin >> l >> r ;
		for(int i = l ; i <= r ;i++){
			s[i] = 1; par[i] =0  ;
			for(int k : di[a[i]]){
				vec[k].pb(i); 
			}
		}
		for(int i = 1; i <=r ; i++){
			if(sz(vec[i]) == 0)continue ;
			int mn = inf , id ;
			for(int z : vec[i]){
				if(mn > t[a[z]]/i){
					id= z ;
					mn = t[a[z]/i];
				}
			}
			for(int z : vec[i]){
				ed[mn+t[z]].pb({id ,z});
			}
		}
		int ans =0 ;
		for(int i =0; i <= 30 ; i++){
			for(pii x : ed[i]){
				if(find(x.F) != find(x.S)){
					x.F = find(x.F) ; x.S = find(x.S);
					if(s[x.F] > s[x.S])swap(x.F , x.S) ;
					par[x.F] = x.S ;
					s[x.S] += s[x.F];
					ans += i ;
				}
			}
		}
		if(ans == 35 && i == 486)cout << l << " " << r << endl ;
		cout << ans << "\n"; 
		for(int i = 1 ; i <= r ; i++){
			vec[i].clear(); 
		}
	}
}
/*


*/#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
vector <int> di[maxn] , vec[maxn] ; 
vector <pii> ed[maxn] ;

int find(int v){
	if(par[v]==0)return v; 
	return par[v] = find(par[v]);
}

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
	for(int i = 1; i <= N ; i++)a[i] = 1;
	for(int i = 2; i <= N ; i++){
		if(mark[i] == 1)continue ;
		for(int j = i ; j <= N ; j+=i){
			mark[j] = 1 ;
			a[j] *= i ;
			t[j]++;
		}
	}
	for(int i = 1; i <= N ; i++){
		if(a[i] != i)continue ;
		for(int j = i ; j <= N ; j+=i){
			if(a[j] == j)di[j].pb(i) ;
		}
	}
	int T ;cin >> T ;
	for(int i = 1; i <= T ; i++){
		for(int i =0 ; i <= 30 ; i++){
			ed[i].clear() ;
		}
		int l  ,r ;
		cin >> l >> r ;
		for(int i = l ; i <= r ;i++){
			s[i] = 1; par[i] =0  ;
			for(int k : di[a[i]]){
				vec[k].pb(i); 
			}
		}
		for(int i = 1; i <=r ; i++){
			if(sz(vec[i]) == 0)continue ;
			int mn = inf , id ;
			for(int z : vec[i]){
				if(mn > t[a[z]]/i){
					id= z ;
					mn = t[a[z]/i];
				}
			}
			for(int z : vec[i]){
				ed[mn+t[z]].pb({id ,z});
			}
		}
		int ans =0 ;
		for(int i =0; i <= 30 ; i++){
			for(pii x : ed[i]){
				if(find(x.F) != find(x.S)){
					x.F = find(x.F) ; x.S = find(x.S);
					if(s[x.F] > s[x.S])swap(x.F , x.S) ;
					par[x.F] = x.S ;
					s[x.S] += s[x.F];
					ans += i ;
				}
			}
		}
		if(ans == 35 && i == 486)cout << l << " " << r << endl ;
		cout << ans << "\n"; 
		for(int i = 1 ; i <= r ; i++){
			vec[i].clear(); 
		}
	}
}
/*


*/
Source code, Language: C++14

Details 

answer.code:97:9: error: redefinition of ‘std::mt19937 rng’
   97 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      |         ^~~
answer.code:11:9: note: ‘std::mt19937 rng’ previously declared here
   11 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      |         ^~~
answer.code:98:11: error: redefinition of ‘const int maxn’
   98 | const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
      |           ^~~~
answer.code:12:11: note: ‘const int maxn’ previously defined here
   12 | const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
      |           ^~~~
answer.code:98:26: error: redefinition of ‘const int N’
   98 | const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
      |                          ^
answer.code:12:26: note: ‘const int N’ previously defined here
   12 | const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
      |                          ^
answer.code:98:36: error: redefinition of ‘const int inf’
   98 | const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
      |                                    ^~~
answer.code:12:36: note: ‘const int inf’ previously defined here
   12 | const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
      |                                    ^~~
answer.code:98:48: error: redefinition of ‘const int mod’
   98 | const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
      |                                                ^~~
answer.code:12:48: note: ‘const int mod’ previously defined here
   12 | const int maxn =1e6+12 , N = 1e6 , inf = 1e9 , mod = 1000000007 ;
      |                                                ^~~
answer.code:99:5: error: redefinition of ‘int t [1000012]’
   99 | int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
      |     ^
answer.code:13:5: note: ‘int t [1000012]’ previously declared here
   13 | int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
      |     ^
answer.code:99:15: error: redefinition of ‘int a [1000012]’
   99 | int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
      |               ^
answer.code:13:15: note: ‘int a [1000012]’ previously declared here
   13 | int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
      |               ^
answer.code:99:25: error: redefinition of ‘int mark [1000012]’
   99 | int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
      |                         ^~~~
answer.code:13:25: note: ‘int mark [1000012]’ previously declared here
   13 | int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
      |                         ^~~~
answer.code:99:38: error: redefinition of ‘int par [1000012]’
   99 | int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
      |                                      ^~~
answer.code:13:38: note: ‘int par [1000012]’ previously declared here
   13 | int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
      |                                      ^~~
answer.code:99:50: error: redefinition of ‘int s [1000012]’
   99 | int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
      |                                                  ^
answer.code:13:50: note: ‘int s [1000012]’ previously declared here
   13 | int t[maxn] , a[maxn] , mark[maxn] , par[maxn] , s[maxn] ;
      |                                                  ^
answer.code:100:14: error: redefinition of ‘std::vector<int> di [1000012]’
  100 | vector <int> di[maxn] , vec[maxn] ;
      |              ^~
answer.code:14:14: note: ‘std::vector<int> di [1000012]’ previously declared here
   14 | vector <int> di[maxn] , vec[maxn] ;
      |              ^~
answer.code:100:25: error: redefinition of ‘std::vector<int> vec [1000012]’
  100 | vector <int> di[maxn] , vec[maxn] ;
      |                         ^~~
answer.code:14:25: note: ‘std::vector<int> vec [1000012]’ previously declared here
   14 | vector <int> di[maxn] , vec[maxn] ;
      |                         ^~~
answer.code:101:14: error: redefinition of ‘std::vector<std::pair<int, int> > ed [1000012]’
  101 | vector <pii> ed[maxn] ;
      |              ^~
answer.code:15:14: note: ‘std::vector<std::pair<int, int> > ed [1000012]’ previously declared here
   15 | vector <pii> ed[maxn] ;
      |              ^~
answer.code:103:5: error: redefinition of ‘int find(int)’
  103 | int find(int v){
      |     ^~~~
answer.code:17:5: note: ‘int find(int)’ previously defined here
   17 | int find(int v){
      |     ^~~~
answer.code:108:8: error: redefinition of ‘int main()’
  108 | signed main() {
      |        ^~~~
answer.code:22:8: note: ‘int main()’ previously defined here
   22 | signed main() {
      |        ^~~~
English 繁體中文 简体中文

Server Time: 2024-12-03 07:39:19 | OpenSource Project