# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
55317 | 2018-07-07T01:06:16 Z | IvanC | Sirni (COCI17_sirni) | C++17 | 5000 ms | 479484 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef tuple<int,int,int> trinca; const int MAXN = 1e7 + 1; int pai[MAXN],proximo[MAXN],N; vector<int> ordenado; vector<trinca> Kruskal; int find(int x){ if(x == pai[x]) return x; return pai[x] = find(pai[x]); } void join(int x,int y){ x = find(x);y = find(y); if(x == y) return; if(rand() & 1) swap(x,y); pai[y] = x; } int main(){ scanf("%d",&N); for(int i = 1;i<=N;i++){ int x; scanf("%d",&x); pai[x] = x; } for(int i = 1;i<MAXN;i++){ if(pai[i] == 0) continue; ordenado.push_back(i); for(int j = 2*i;j<MAXN;j+=i) if(pai[j] != 0) join(i,j); } int ultimo_visto = ordenado.back(); for(int i = MAXN-1;i>=1;i--){ proximo[i] = ultimo_visto; if(!ordenado.empty() && ordenado.back() == i){ ultimo_visto = i; ordenado.pop_back(); } } for(int i = 1;i<MAXN;i++){ if(pai[i] == 0) continue; ultimo_visto = -1; for(int j = i;j<MAXN;j+=i){ int candidato = proximo[j]; if(candidato == ultimo_visto) continue; ultimo_visto = candidato; Kruskal.push_back(make_tuple(candidato % i,i,candidato)); } } sort(Kruskal.begin(),Kruskal.end()); ll total = 0; for(trinca davez : Kruskal){ int w = get<0>(davez),u = get<1>(davez),v = get<2>(davez); if(find(u) != find(v)){ join(u,v); total += w; } } printf("%lld\n",total); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 82 ms | 43256 KB | Output is correct |
2 | Correct | 184 ms | 44828 KB | Output is correct |
3 | Correct | 87 ms | 44828 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 212 ms | 44828 KB | Output is correct |
2 | Correct | 533 ms | 44828 KB | Output is correct |
3 | Correct | 86 ms | 44828 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 83 ms | 44828 KB | Output is correct |
2 | Correct | 83 ms | 44828 KB | Output is correct |
3 | Correct | 88 ms | 44828 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 580 ms | 69372 KB | Output is correct |
2 | Correct | 1733 ms | 94768 KB | Output is correct |
3 | Correct | 817 ms | 94768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 151 ms | 94768 KB | Output is correct |
2 | Correct | 1132 ms | 94768 KB | Output is correct |
3 | Correct | 712 ms | 94768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1206 ms | 96300 KB | Output is correct |
2 | Correct | 2165 ms | 146636 KB | Output is correct |
3 | Correct | 669 ms | 146636 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 488 ms | 146636 KB | Output is correct |
2 | Correct | 2246 ms | 147676 KB | Output is correct |
3 | Correct | 684 ms | 147676 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 556 ms | 147676 KB | Output is correct |
2 | Execution timed out | 5207 ms | 342032 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 502 ms | 342032 KB | Output is correct |
2 | Execution timed out | 5071 ms | 479484 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 163 ms | 479484 KB | Output is correct |
2 | Execution timed out | 5040 ms | 479484 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |