Submission #582285

#TimeUsernameProblemLanguageResultExecution timeMemory
582285Ronin13Sirni (COCI17_sirni)C++14
112 / 140
5100 ms608676 KiB
#include<bits/stdc++.h> #define ll long long #define ull unsigned ll #define f first #define s second #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back using namespace std; void lastshot(){ cout << "FUCK THIS SHIT I'M OUT!\n"; } void debug(){ cout << "WHAT A STUPID\n"; } //WELCOME TO PROJECT MAYHEM // rule #1: You don't ask questions about project MAYHEM // rule #2: You don't ask questions about project MAYHEM const int PMAX = 1e7 + 5; const int NMAX = 2e5 + 1; int p[PMAX]; int last[PMAX]; int par[NMAX]; int sz[NMAX]; void make_set(int v){ par[v] = v; sz[v] = 1; } int find_set(int v){ return par[v] == v ? v : par[v] = find_set(par[v]); } void union_sets(int a, int b){ a = find_set(a); b = find_set(b); if(a != b){ if(sz[a] < sz[b]) swap(a, b); par[b] = a; sz[a] += sz[b]; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; set <int> st; for(int i = 1; i <= n; i++){ int x; cin >> x; st.insert(x); } int ind = 0; for(int to : st){ p[to] = ++ind; } int l = 10000001; for(int i = 10000000; i >= 1; i--){ if(p[i]) last[i] = i, l = i; else last[i] = l; } // cout << 1; ind = 1; vector <pair <ll, pii> > edges; for(int to : st){ int x = last[to + 1]; if(x < 2 * to && x < 1e7 + 1) edges.pb({x - to, {ind, p[x]}}); for(int i = 2 * to; i <= 1e7; i += to){ x = last[i]; if(x > 1e7) break; if(x > 1e7 || x >= i + to) continue; edges.pb({x - i, {p[x], ind}}); } ind++; } //cout << 1; for(int i = 1; i < ind; i++){ make_set(i); } sort(edges.begin(), edges.end()); ll sum = 0; int cnt = 0; for(int i = 0; i < edges.size(); i++){ // cout << to.f << ' ' << to.s.f << ' ' << to.s.s << "\n"; int x = edges[i].s.f, y = edges[i].s.s; if(cnt == ind - 1) break; if(find_set(x) == find_set(y)) continue; union_sets(x, y); cnt++; sum += edges[i].f; } cout << sum; return 0; }

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < edges.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
#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...