Submission #799435

#TimeUsernameProblemLanguageResultExecution timeMemory
799435BaytoroSirni (COCI17_sirni)C++17
140 / 140
4350 ms758104 KiB
#include <bits/stdc++.h> using namespace std; #define ios ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define fr first #define sc second #define endl "\n" #define ll long long //#define int long long void fopn(string name){ freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout); } const ll INF=1e18,mod=1e9,N=1e7+5; int n; int ans=0,par[N]; int f(int x){ if(par[x]==x) return x; return par[x]=f(par[x]); } vector<pair<int,int>> g[N]; void add(int a, int b, int c){ a=f(a);b=f(b); if(a==b) return; ans+=c; if(rand()%2) swap(a,b); par[a]=b; } void solve(){ int n;cin>>n; vector<int> p(n); for(int i=0;i<n;i++){ cin>>p[i]; } for(int i=1;i<=1e7;i++) par[i]=i; sort(all(p)); for(int i=0;i<n;i++){ int j=i+1; for(int cur=p[i];cur<=1e7;cur+=p[i]){ while(j<n && p[j]<cur) j++; if(j<n) g[p[j]%p[i]].pb({i,j}); j++; } } for(int i=0;i<=1e7;i++){ for(auto it: g[i]) add(it.fr,it.sc,i); } cout<<ans<<endl; } main(){ ios; int T=1; //cin>>T; for(int i=1;i<=T;i++){ //cout<<"Case #"<<i<<": "; solve(); } }

Compilation message (stderr)

sirni.cpp:54:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   54 | main(){
      | ^~~~
sirni.cpp: In function 'void fopn(std::string)':
sirni.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...