제출 #1122328

#제출 시각아이디문제언어결과실행 시간메모리
1122328dostsSirni (COCI17_sirni)C++17
0 / 140
2452 ms786432 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") using namespace std; //#define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define all(cont) cont.begin(),cont.end() #define vi vector<int> int MOD = 1e9+7,inf = 2e18; const int N = 1e5+50,Q = 2e5+50; struct DSU { vi dad,sz; DSU(int nn) { dad.resize(nn+1); iota(all(dad),0ll); sz.assign(nn+1,1); } int find(int x) { if (x == dad[x]) return x; return dad[x] = find(dad[x]); } void unite(int x,int y) { int a = find(x),b = find(y); if (a == b) return; if (sz[a] < sz[b]) swap(a,b); dad[b] = a; sz[a]+=sz[b]; } }; vi have[10000001]; int orig[10000001]; struct Edge { int u,v,w; }; void solve() { int n; cin >> n; vi p(n); for (int i=0;i<n;i++) cin >> p[i]; sort(p.begin(),p.end()); vi pp; for (int i = 0;i<n;i++) if (!i || p[i] != p[i-1]) pp.push_back(p[i]); n = pp.size(); for (int i = 0;i<n;i++) { orig[pp[i]] = i+1; for (int j = pp[i];j<=10000000;j+=pp[i]) have[j].push_back(i+1); } vector<pii> collect; vector<Edge> edges; long long ans = 0; for (int i = 1;i<=10000000;i++) { for (auto it : have[i]) collect.push_back({it,i}); if (orig[i]) { for (auto it : collect) { if (it.ff != orig[i]) { edges.push_back(Edge{it.ff,orig[i],i-it.ss}); } } collect.clear(); } } sort(all(edges),[&](const Edge& e1,const Edge& e2) { return e1.w < e2.w; }); DSU dsu(n); for (auto it : edges) { if (dsu.find(it.u) != dsu.find(it.v)) { dsu.unite(it.u,it.v); ans+=it.w; } } cout << ans << '\n'; } int32_t main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }

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

sirni.cpp:12:23: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   12 | int MOD = 1e9+7,inf = 2e18;
      |                       ^~~~
#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...