# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
55320 | 2018-07-07T01:15:14 Z | IvanC | Sirni (COCI17_sirni) | C++17 | 5000 ms | 520284 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> ii; const int MAXN = 1e7 + 1; int pai[MAXN],proximo[MAXN],N,conjuntos; vector<int> ordenado; vector<ii> Kruskal[MAXN]; 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; conjuntos--; 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); if(pai[x] == x) continue; pai[x] = x; conjuntos++; } 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(); } } if(conjuntos == 1){ printf("0\n"); return 0; } 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[candidato % i].push_back(ii(i,candidato)); } } ll total = 0; for(int w = 0;w<MAXN && conjuntos > 1;w++){ for(ii davez : Kruskal[w]){ int u = davez.first, v = davez.second; 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 | 297 ms | 278136 KB | Output is correct |
2 | Correct | 410 ms | 278756 KB | Output is correct |
3 | Correct | 301 ms | 278756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 433 ms | 278756 KB | Output is correct |
2 | Correct | 847 ms | 278756 KB | Output is correct |
3 | Correct | 298 ms | 278756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 307 ms | 278768 KB | Output is correct |
2 | Correct | 299 ms | 278768 KB | Output is correct |
3 | Correct | 301 ms | 278768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 756 ms | 290276 KB | Output is correct |
2 | Correct | 1718 ms | 315072 KB | Output is correct |
3 | Correct | 758 ms | 315072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 382 ms | 315072 KB | Output is correct |
2 | Correct | 1387 ms | 315072 KB | Output is correct |
3 | Correct | 905 ms | 315072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1273 ms | 315072 KB | Output is correct |
2 | Correct | 1954 ms | 330020 KB | Output is correct |
3 | Correct | 805 ms | 330020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 774 ms | 330020 KB | Output is correct |
2 | Correct | 2174 ms | 330020 KB | Output is correct |
3 | Correct | 747 ms | 330020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 751 ms | 330020 KB | Output is correct |
2 | Correct | 4727 ms | 520284 KB | Output is correct |
3 | Correct | 803 ms | 520284 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 649 ms | 520284 KB | Output is correct |
2 | Execution timed out | 5102 ms | 520284 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 411 ms | 520284 KB | Output is correct |
2 | Execution timed out | 5062 ms | 520284 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |