제출 #1122377

#제출 시각아이디문제언어결과실행 시간메모리
1122377dostsSirni (COCI17_sirni)C++17
98 / 140
3499 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; } int sm = 0; for (int i = 1;i<n;i++) sm+=pp[i]%pp[i-1]; vi collect; vector<Edge> edges; int lasttake[n+1]{0}; long long ans = 0; for (int i = 1;i<=10000000;i++) { for (auto it : have[i]) { if (!lasttake[it]) collect.push_back(it); lasttake[it] = i; } //cout << "I" sp i << endl; if (orig[i]) { if (!lasttake[orig[i]]) collect.push_back(orig[i]); lasttake[orig[i]] = i; have[i].push_back(orig[i]); //for (auto it : collect) cout << it.ff sp it.ss << '\n'; for (auto it : collect) { if (it != orig[i]) { if (i-lasttake[it] <= sm) edges.push_back(Edge{it,orig[i],i-lasttake[it]}); } } for (auto it : collect) lasttake[it] = 0; collect.clear(); if (!lasttake[orig[i]]) collect.push_back(orig[i]); lasttake[orig[i]] = i; } for (auto it : have[i]) { if (i+pp[it-1] <= 10000000) have[i+pp[it-1]].push_back(it); } have[i].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...