| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 736161 |
2023-05-05T09:11:23 Z |
marvinthang |
Sirni (COCI17_sirni) |
C++17 |
|
3368 ms |
612756 KB |
/******************************
* author : @marvinthang *
* date : 09 / 02 / 2022 *
******************************/
#include <bits/stdc++.h>
using namespace std;
#define superspeed ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '{'; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << '}'; }
const int MOD = 1e9 + 7;
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {0, 1, 0, -1, 0}; // {0, 1, 1, -1, -1, 1, 0, -1, 0};
const long long oo = 1e18;
const int MAX = 1e5 + 5;
const int MAX_VAL = 1e7 + 7;
struct DisjointSet {
static const int MAXN = 1e5 + 5;
int par[MAXN] = {};
DisjointSet(int n = 0) {
for (int i = 1; i <= n; ++i) par[i] = -1;
}
int find(int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
bool join(int u, int v) {
if ((u = find(u)) == (v = find(v))) return false;
if (par[u] > par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
return true;
}
};
int N, P[MAX], near[MAX_VAL], pos[MAX_VAL];
vector <pair <int, int>> edges[MAX_VAL];
int main(void) {
superspeed;
file("coci1617_r6_sirni");
cin >> N;
int maxVal = 0;
for (int i = 1; i <= N; ++i) cin >> P[i], maxVal = max(maxVal, P[i]), near[P[i]] = P[i];
sort(P + 1, P + 1 + N);
N = unique(P + 1, P + 1 + N) - P - 1;
for (int i = 1; i <= N; ++i) pos[P[i]] = i;
for (int i = maxVal; i >= 0; --i)
if (!near[i]) near[i] = near[i + 1];
for (int i = 1; i <= N; ++i) {
if (near[P[i] + 1] && P[i] + 1 <= maxVal && near[P[i]] < P[i] << 1)
edges[near[P[i] + 1] % P[i]].push_back(make_pair(pos[P[i]], pos[near[P[i] + 1]]));
for (int k = P[i] << 1; k <= maxVal; k += P[i]) {
if (!near[k] || near[k] >= k + P[i]) continue;
edges[near[k] % P[i]].push_back(make_pair(pos[P[i]], pos[near[k]]));
}
}
DisjointSet dsu(N);
long long res = 0;
for (int i = 0; i <= maxVal; ++i) {
for (auto [u, v]: edges[i]) {
if (dsu.join(u, v)) res += i;
}
}
cout << res << '\n';
return 0;
}
Compilation message
sirni.cpp: In function 'int main()':
sirni.cpp:11:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | #define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:53:5: note: in expansion of macro 'file'
53 | file("coci1617_r6_sirni");
| ^~~~
sirni.cpp:11:95: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | #define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:53:5: note: in expansion of macro 'file'
53 | file("coci1617_r6_sirni");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
174 ms |
278312 KB |
Output is correct |
| 2 |
Correct |
207 ms |
278944 KB |
Output is correct |
| 3 |
Correct |
179 ms |
278804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
235664 KB |
Output is correct |
| 2 |
Correct |
430 ms |
275780 KB |
Output is correct |
| 3 |
Correct |
175 ms |
278764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
168 ms |
278672 KB |
Output is correct |
| 2 |
Correct |
179 ms |
277000 KB |
Output is correct |
| 3 |
Correct |
173 ms |
278768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
253872 KB |
Output is correct |
| 2 |
Correct |
279 ms |
281120 KB |
Output is correct |
| 3 |
Correct |
186 ms |
259080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
245044 KB |
Output is correct |
| 2 |
Correct |
258 ms |
265140 KB |
Output is correct |
| 3 |
Correct |
160 ms |
250016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
246 ms |
266064 KB |
Output is correct |
| 2 |
Correct |
332 ms |
295816 KB |
Output is correct |
| 3 |
Correct |
189 ms |
257368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
240740 KB |
Output is correct |
| 2 |
Correct |
342 ms |
290400 KB |
Output is correct |
| 3 |
Correct |
187 ms |
257016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
321 ms |
326856 KB |
Output is correct |
| 2 |
Correct |
1569 ms |
523212 KB |
Output is correct |
| 3 |
Correct |
355 ms |
329268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
328 ms |
326816 KB |
Output is correct |
| 2 |
Correct |
3273 ms |
612756 KB |
Output is correct |
| 3 |
Correct |
380 ms |
333248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
311228 KB |
Output is correct |
| 2 |
Correct |
3368 ms |
601552 KB |
Output is correct |
| 3 |
Correct |
206 ms |
258884 KB |
Output is correct |
