# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
55322 | 2018-07-07T01:17:26 Z | IvanC | Sirni (COCI17_sirni) | C++17 | 5000 ms | 521500 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(x > y) 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 | 274 ms | 278136 KB | Output is correct |
2 | Correct | 371 ms | 278756 KB | Output is correct |
3 | Correct | 275 ms | 278756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 368 ms | 278756 KB | Output is correct |
2 | Correct | 778 ms | 278756 KB | Output is correct |
3 | Correct | 288 ms | 278756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 295 ms | 278756 KB | Output is correct |
2 | Correct | 301 ms | 278756 KB | Output is correct |
3 | Correct | 295 ms | 278756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 654 ms | 290176 KB | Output is correct |
2 | Correct | 1392 ms | 315088 KB | Output is correct |
3 | Correct | 776 ms | 315088 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 358 ms | 315088 KB | Output is correct |
2 | Correct | 1266 ms | 315088 KB | Output is correct |
3 | Correct | 794 ms | 315088 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1190 ms | 315088 KB | Output is correct |
2 | Correct | 1826 ms | 329856 KB | Output is correct |
3 | Correct | 707 ms | 329856 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 741 ms | 329856 KB | Output is correct |
2 | Correct | 1626 ms | 329856 KB | Output is correct |
3 | Correct | 600 ms | 329856 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 529 ms | 329856 KB | Output is correct |
2 | Correct | 4445 ms | 519712 KB | Output is correct |
3 | Correct | 640 ms | 519712 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 599 ms | 519712 KB | Output is correct |
2 | Execution timed out | 5115 ms | 521500 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 386 ms | 521500 KB | Output is correct |
2 | Execution timed out | 5031 ms | 521500 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |