# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
55316 | 2018-07-07T00:22:05 Z | IvanC | Sirni (COCI17_sirni) | C++17 | 1118 ms | 107788 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] != i) continue; ordenado.push_back(i); } 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] != i) 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 | Incorrect | 80 ms | 43512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 165 ms | 43512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 85 ms | 43876 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 587 ms | 70004 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 146 ms | 70004 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1118 ms | 95380 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 431 ms | 95380 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 558 ms | 107132 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 531 ms | 107788 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 184 ms | 107788 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |