제출 #573164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573164		codebuster_10	Sirni (COCI17_sirni)	C++17	140 / 140	3870 ms	785344 KiB

sirni

#include <bits/stdc++.h>
// #define int int64_t //be careful about this 
 
using namespace std;
 
#define vt vector 
#define ar array 
#define pr pair 
 
#define f first 
#define s second
 
#define pb push_back
#define eb emplace_back
 
#define fr(i,a,b) for(int i = a; i < b; ++i)
#define rf(i,a,b) for(int i = b-1; i >= a; --i)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
 
namespace IN{
  template<class T> void re(vector<T> &A);
  template<class S,class T> void re(pair<S,T> &A);
  template<class T,size_t N> void re(array<T,N> &A);
 
  template<class T> void re(T& x){ 
    cin >> x;}
  template<class H, class... T> void re(H& h, T&... t){ 
    re(h); re(t...);}
 
  template<class T> void re(vector<T> &A){ 
    for(auto& x : A) re(x);}
  template<class S,class T> void re(pair<S,T> &A){ 
      re(A.first); re(A.second);}
  template<class T,size_t N> void re(array<T,N> &A){
    for(int i = 0; i < N; ++i)  re(A[i]);}
}
 
namespace OUT{
  template<class T>
  void __p(const T& a){ cout<<a; }
  template<class T, class F>
  void __p(const pair<T, F>& a){ cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; }
  template<class T, size_t N>
  void __p(const array<T,N>& a){ cout<<"{"; for(int i=0;i<N;++i)__p(a[i]),cout<<",}\n"[i+1==N]; }
  template<class T>
  void __p(const vector<T>& a){
    cout<<"{";for(auto it=a.begin();it<a.end();it++)__p(*it),cout<<",}\n"[it+1==a.end()]; }
  template<class T, class ...Arg>
  void __p(T a1, Arg ...a){__p(a1); __p(a...); }
  template<class Arg1>
  void __f(const char *s, Arg1 &&arg1){ cout<<s<<" : "; __p(arg1); cout<<endl; }
  template<class Arg1, class ... Args>
  void __f(const char *ss, Arg1 &&arg1, Args &&... args){
    int b=0,i=0; do{ if(ss[i]=='(') b++; if(ss[i]==')') b--; i++;}while(!(ss[i]==','&&b==0));
    const char *comma=ss+i; cout.write(ss,comma-ss)<<" : ";__p(arg1);cout<<" | ";__f(comma+1,args...);}
  #define trace(...) cout<<"Line:"<<__LINE__<<"  ", __f(#__VA_ARGS__, __VA_ARGS__)
}
 
 
namespace FUNC{
  void IO(string s = ""){
    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.precision(20); 
    cout << fixed;
    if(!s.empty()){
      freopen((s+".in").c_str(),"r",stdin);
      freopen((s+".out").c_str(),"w",stdout);
    }
  }
 
  const auto start_time = chrono::high_resolution_clock::now();
  void output_run_time(){
    // will work for ac,cc&&cf.
#ifndef ONLINE_JUDGE
    auto end_time = chrono::high_resolution_clock::now();
    chrono::duration<double> diff = end_time-start_time;
      cout << "\n\n\nTime Taken : " << diff.count();
#endif
  }
 
  template<class T> bool ckmin(T& a, const T& b){ 
    return b < a ? a = b, true : false; }
    
  template<class T> bool ckmax(T& a, const T& b){ 
    return a < b ? a = b, true : false; }
 
  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  int my_rand(int L, int R){ 
    return uniform_int_distribution<int>(L,R)(rng); }
  
  template<class T> int sz(const T& x){ 
    return int(x.size()); }
 
  template<class T> int lb(const vector<T>& vec,const T& val){
    return int(lower_bound(vec.begin(), vec.end(),val) - vec.begin()); }
 
  template<class T> int ub(const vector<T>& vec,const T& val){
    return int(upper_bound(vec.begin(), vec.end(),val) - vec.begin()); }
 
  constexpr int  dx[4] = {1,0,-1,0};
  constexpr int  dy[4] = {0,1,0,-1};
  constexpr char dr[4] = {'D','R','U','L'};
 
  constexpr long long INFLL1 = 1e16, INFLL2 = 9e18;
  constexpr int INF = 2e9;
 
  template<class T>
  vector<T> V(int n,T val){
    return vector<T> (n,val);
  }
 
  template<class T>
  vector<vector<T>> V(int n,int m,T val){
    return vector<vector<T>> (n,vector<T> (m,val));
  }
 
  template<class T>
  vector<vector<vector<T>>> V(int n,int m,int k,T val){
    return vector<vector<vector<T>>> (n,vector<vector<T>> (m,vector<T> (k,val)));
  }
}
 
 
using namespace IN;
using namespace OUT;
using namespace FUNC;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
struct DSU {
  int n, z;
  // root node: -1 * component size
  // otherwise: parent
  vector<int> parent_or_size;
 
  DSU(int n) : n(n), parent_or_size(n, -1), z(n) {}
 
  bool merge(int a, int b){
    int x = leader(a), y = leader(b);
    if(x == y) 
      return false;
    if(-parent_or_size[x] < -parent_or_size[y]) 
      swap(x, y);
    parent_or_size[x] += parent_or_size[y];
    parent_or_size[y] = x;
    z--;
    return true;
  }
 
  bool same(int a, int b){
    return leader(a) == leader(b);
  }
 
  int leader(int a){
    if(parent_or_size[a] < 0) 
      return a;
    return parent_or_size[a] = leader(parent_or_size[a]);
  }
 
  int size(int a){
    return -parent_or_size[leader(a)];
  }
  
  vector<vector<int>> groups(){
    vector<int> leader_buf(n), group_size(n);
    for(int i = 0; i < n; i++){
      leader_buf[i] = leader(i);
      group_size[leader_buf[i]]++;
    }
    vector<vector<int>> result(n);
    for(int i = 0; i < n; i++){
      result[i].reserve(group_size[i]);
    }
    for(int i = 0; i < n; i++){
      result[leader_buf[i]].push_back(i);
    }
    result.erase(remove_if(result.begin(), result.end(),[&](const auto& v){return v.empty(); }),result.end());
    return result;
  }
 
  int comp(){
    return z;
  }
};
 
 
 
signed main(){
  IO();
  
  int n;
  re(n);
 
  vt<int> p(n);
  re(p);
 
  sort(all(p));
  p.erase(unique(all(p)),p.end());
 
  n = sz(p);
 
  int N = p.back();
 
  vt<int> ip(N+1,-1);
 
  fr(i,0,n){
    ip[p[i]] = i;
  }
 
  vt<int> lb(N+1);
 
  rf(i,0,N+1){
    if(ip[i] >= 0)
      lb[i] = ip[i];
    else
      lb[i] = lb[i+1];
  }
 
  vt<pr<int,int>> edges[N+1];

  auto f = [&](pr<int,int> P){
    P.f = p[P.f];
    P.s = p[P.s];
    return min(P.f%P.s,P.s%P.f);
  };
 
  fr(i,0,n){
    if(i+1 < n){
      edges[f({i+1,i})].pb({i+1,i});
    }
    for(int r = 0; r * p[i] <= N; ++r){
      int x = lb[r*p[i]];
      edges[f({x,i})].pb({x,i}); 
    }
  }

  
 
  DSU dsu(n);
 
  long long cost = 0;

  for(int w = 0; w <= N; ++w)
    for(auto [u,v] : edges[w])
      if(dsu.merge(u,v))
        cost += w;
 
  cout << cost;
 
 
 
  
 
 
 
 
 
 
 
 
 
  //output_run_time();
  return 0;
}
 
 
 
 

컴파일 시 표준 에러 (stderr) 메시지

sirni.cpp: In constructor 'DSU::DSU(int)':
sirni.cpp:150:15: warning: 'DSU::parent_or_size' will be initialized after [-Wreorder]
  150 |   vector<int> parent_or_size;
      |               ^~~~~~~~~~~~~~
sirni.cpp:147:10: warning:   'int DSU::z' [-Wreorder]
  147 |   int n, z;
      |          ^
sirni.cpp:152:3: warning:   when initialized here [-Wreorder]
  152 |   DSU(int n) : n(n), parent_or_size(n, -1), z(n) {}
      |   ^~~
sirni.cpp: In function 'void FUNC::IO(std::string)':
sirni.cpp:68:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |       freopen((s+".in").c_str(),"r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:69:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |       freopen((s+".out").c_str(),"w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14