# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
126466 | 2019-07-07T19:46:51 Z | letrongdat | Sirni (COCI17_sirni) | C++17 | 5000 ms | 574368 KB |
#include <bits/stdc++.h> using namespace std; #define forn(i, a, b) for(int i=a; i<=b; ++i) #define ford(i, a ,b) for(int i=a; i>=b; --i) #define repn(i, a, b) for(int i=a; i <b; ++i) typedef pair<int, int> ii; const int maxM = 1e7+ 10; const int maxN = 1e5 +10; int N; int Near[maxM]; int lab[maxN]; vector<int> P; vector<ii> Edge[maxM]; int root(int u) { if (lab[u] < 0) return u; return lab[u] = root(lab[u]); } void join(int u, int v) { int l1 = root(u), l2 = root(v); if (lab[l1] > lab[l2]) swap(l1, l2); lab[l1] += lab[l2]; lab[l2] = l1; } int main() { // #ifndef ONLINE_JUDGE // freopen("a.inp", "r", stdin); // #endif // ONLINE_JUDGE ios::sync_with_stdio(0); memset(lab, -1, sizeof lab); cin >> N; P.resize(N); repn(i, 0, N) cin >> P[i]; sort(P.begin(), P.end()); P.resize(unique(P.begin(), P.end()) - P.begin()); memset(Near, 0x3f, sizeof Near); repn(i, 0, P.size()) Near[P[i]] = i; ford(i, P.back(), 0) Near[i] = min(Near[i], Near[i+1]); repn(i, 0, P.size() -1) { int weight = P[Near[P[i]+1]] - P[i]; if (weight < P[i]) Edge[weight].push_back({i, Near[P[i]+1]}); for(int j = 2*P[i]; j <= P.back(); j += P[i]) { int weight = P[Near[j]] - j; if (weight < P[i]) Edge[weight].push_back({i, Near[j]}); } } long long result = 0; repn(i, 0, maxM) { for(auto &e: Edge[i]) if (root(e.first) == root(e.second)) continue; else { result += i; join(e.first, e.second); } } cout << result; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 308 ms | 274936 KB | Output is correct |
2 | Correct | 362 ms | 277112 KB | Output is correct |
3 | Correct | 367 ms | 275044 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 278 ms | 274936 KB | Output is correct |
2 | Correct | 588 ms | 275576 KB | Output is correct |
3 | Correct | 310 ms | 274912 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 310 ms | 274940 KB | Output is correct |
2 | Correct | 310 ms | 274844 KB | Output is correct |
3 | Correct | 310 ms | 274936 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 362 ms | 284696 KB | Output is correct |
2 | Correct | 572 ms | 312060 KB | Output is correct |
3 | Correct | 383 ms | 290160 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 302 ms | 276472 KB | Output is correct |
2 | Correct | 480 ms | 297320 KB | Output is correct |
3 | Correct | 370 ms | 284860 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 444 ms | 296996 KB | Output is correct |
2 | Correct | 595 ms | 326920 KB | Output is correct |
3 | Correct | 375 ms | 288252 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 304 ms | 278272 KB | Output is correct |
2 | Correct | 589 ms | 321100 KB | Output is correct |
3 | Correct | 371 ms | 288364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 504 ms | 287480 KB | Output is correct |
2 | Correct | 3539 ms | 482964 KB | Output is correct |
3 | Correct | 533 ms | 289908 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 496 ms | 287180 KB | Output is correct |
2 | Execution timed out | 5143 ms | 574368 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 338 ms | 276984 KB | Output is correct |
2 | Execution timed out | 5064 ms | 545556 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |