# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
126462 | 2019-07-07T19:35:18 Z | letrongdat | Sirni (COCI17_sirni) | C++17 | 5000 ms | 574180 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]); } bool join(int u, int v) { int l1 = root(u), l2 = root(v); if (l1 == l2) return false; if (lab[l1] > lab[l2]) swap(l1, l2); lab[l1] += lab[l2]; lab[l2] = l1; return true; } int main() { 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]; 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]) continue; Edge[weight].push_back({i, Near[j]}); } } long long result = 0, cnt = 0; repn(i, 0, maxM) { if (cnt == P.size() -1) break; for(auto &e: Edge[i]) if (join(e.first, e.second)) { result += i; cnt ++; } } cout << result; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 291 ms | 274908 KB | Output is correct |
2 | Correct | 333 ms | 277240 KB | Output is correct |
3 | Correct | 289 ms | 275064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 268 ms | 274808 KB | Output is correct |
2 | Correct | 603 ms | 275448 KB | Output is correct |
3 | Correct | 283 ms | 275064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 281 ms | 274816 KB | Output is correct |
2 | Correct | 287 ms | 274896 KB | Output is correct |
3 | Correct | 282 ms | 274936 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 334 ms | 284652 KB | Output is correct |
2 | Correct | 508 ms | 311652 KB | Output is correct |
3 | Correct | 353 ms | 289880 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 261 ms | 276216 KB | Output is correct |
2 | Correct | 440 ms | 297012 KB | Output is correct |
3 | Correct | 326 ms | 284732 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 419 ms | 296812 KB | Output is correct |
2 | Correct | 592 ms | 325700 KB | Output is correct |
3 | Correct | 371 ms | 288180 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 285 ms | 278232 KB | Output is correct |
2 | Correct | 593 ms | 320956 KB | Output is correct |
3 | Correct | 380 ms | 288144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 572 ms | 287124 KB | Output is correct |
2 | Correct | 3202 ms | 483276 KB | Output is correct |
3 | Correct | 517 ms | 289804 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 481 ms | 286904 KB | Output is correct |
2 | Execution timed out | 5052 ms | 574180 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 321 ms | 277040 KB | Output is correct |
2 | Execution timed out | 5044 ms | 565384 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |