Submission #626534

#TimeUsernameProblemLanguageResultExecution timeMemory
626534Do_you_copySirni (COCI17_sirni)C++17
140 / 140
3084 ms536168 KiB
#include <bits/stdc++.h> //#define int long long #define fi first #define se second #define pb push_back #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using ull = unsigned ll; using ld = long double; using pii = pair <int, int>; using pil = pair <int, ll>; using pli = pair <ll, int>; using pll = pair <ll, ll>; mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count()); ll min(const ll &a, const ll &b){ return (a < b) ? a : b; } ll max(const ll &a, const ll &b){ return (a > b) ? a : b; } //const ll Mod = 1000000007; //const ll Mod2 = 999999999989; //only use when required const int maxN = 1e5 + 1; int n; vector <int> a; vector <vector <pii>> edge; struct TDSU{ vector <pii> save; vector <int> lab; TDSU(){} TDSU(int _n){ lab.resize(_n, -1); } inline void resize(int _n){ lab.resize(_n, -1); } inline int find_set(int u){ if (lab[u] < 0) return u; return lab[u] = find_set(lab[u]); } inline int find(int u){ if (lab[u] < 0) return u; return find(lab[u]); } inline void merge(int u, int v){ if (lab[u] > lab[v]) swap(u, v); save.pb({v, lab[v]}); lab[u] += lab[v]; lab[v] = u; } inline void undo(){ int v = save.back().fi; int u = lab[v]; lab[v] = save.back().se; lab[u] -= lab[v]; save.pop_back(); } inline void clear(){ lab.clear(); save.clear(); } inline void reset(int _n){ clear(); resize(_n); } inline void roll_back(int _n){ while (save.size() > _n) undo(); } }; TDSU dsu; void Init(){ cin >> n; for (int i = 1; i <= n; ++i){ int x; cin >> x; a.pb(x); } sort(a.begin(), a.end()); a.resize(unique(a.begin(), a.end()) - a.begin()); edge.resize(a.back() + 1); for (int _ = 0; _ < a.size() - 1; ++_){ int i = a[_], j = 1; while (i * j <= a.back()){ int k; if (j == 1) k = upper_bound(a.begin(), a.end(), i) - a.begin(); else k = lower_bound(a.begin(), a.end(), i * j) - a.begin(); edge[a[k] % i].pb({_, k}); j = a[k] / i + 1; } } dsu.resize(n); ll ans = 0; for (int i = 0; i <= a.back(); ++i){ for (auto e: edge[i]){ int u = e.fi, v = e.se; int x = dsu.find_set(u), y = dsu.find_set(v); if (x == y && dsu.lab[x] == -n){ cout << ans; return; } else if (x != y){ ans += i; dsu.merge(x, y); } } } cout << ans << "\n"; } #define debu #define taskname "test" signed main(){ if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); #ifdef debug freopen(taskname".out", "w", stdout); #endif } faster; ll tt = 1; //cin >> tt; while (tt--){ Init(); } if (fopen("timeout.txt", "r")){ ofstream timeout("timeout.txt"); timeout << 1000 * double(clock()) / CLOCKS_PER_SEC; #ifndef debug cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n"; #endif } }

Compilation message (stderr)

sirni.cpp: In member function 'void TDSU::roll_back(int)':
sirni.cpp:74:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |         while (save.size() > _n) undo();
      |                ~~~~~~~~~~~~^~~~
sirni.cpp: In function 'void Init()':
sirni.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int _ = 0; _ < a.size() - 1; ++_){
      |                     ~~^~~~~~~~~~~~~~
sirni.cpp: In function 'int main()':
sirni.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...