# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
46348 | 2018-04-19T17:20:35 Z | evpipis | Sirni (COCI17_sirni) | C++ | 5000 ms | 786432 KB |
#include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define mp make_pair typedef pair<int, int> ii; typedef long long ll; const int len = 1e7+5; int cnt[len], nex[2][len], p[len], r[len]; vector<ii> vec[len]; int fin(int i){ if (p[i] == i) return i; return p[i] = fin(p[i]); } void join(int i, int j){ if (r[i] > r[j]) p[j] = i; else{ p[i] = j; if (r[i] == r[j]) r[j]++; } } int main(){ int n, m = 0, k = 0; scanf("%d", &n); for (int i = 0; i < n; i++){ int temp; scanf("%d", &temp); m = max(m, temp); if (!cnt[temp]) cnt[temp] = ++k; } for (int i = m; i >= 1; i--){ nex[0][i] = nex[0][i+1]; if (cnt[i]) nex[0][i] = i; nex[1][i] = nex[1][i+1]; if (cnt[i+1]) nex[1][i] = i+1; } for (int i = 1; i <= k; i++){ r[i] = 0; p[i] = i; } for (int i = 1; i <= m; i++) if (cnt[i]) for (int j = i; j <= m; j+=i){ if (j == i && nex[1][j]) vec[nex[1][j]%i].pb(mp(cnt[i], cnt[nex[1][j]])); else if (j != i && nex[0][j]) vec[nex[0][j]%i].pb(mp(cnt[i], cnt[nex[0][j]])); } ll ans = 0; for (int i = 0; i <= m; i++) for (int j = 0; j < vec[i].size(); j++){ int x = fin(vec[i][j].fi), y = fin(vec[i][j].se); if (x != y) join(x, y), ans += i; } printf("%lld\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 317 ms | 317176 KB | Output is correct |
2 | Correct | 869 ms | 344400 KB | Output is correct |
3 | Correct | 337 ms | 344400 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 205 ms | 344400 KB | Output is correct |
2 | Runtime error | 1590 ms | 786432 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 351 ms | 786432 KB | Output is correct |
2 | Correct | 340 ms | 786432 KB | Output is correct |
3 | Correct | 334 ms | 786432 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 307 ms | 786432 KB | Output is correct |
2 | Correct | 629 ms | 786432 KB | Output is correct |
3 | Correct | 359 ms | 786432 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 237 ms | 786432 KB | Output is correct |
2 | Correct | 427 ms | 786432 KB | Output is correct |
3 | Correct | 273 ms | 786432 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 387 ms | 786432 KB | Output is correct |
2 | Correct | 558 ms | 786432 KB | Output is correct |
3 | Correct | 325 ms | 786432 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 230 ms | 786432 KB | Output is correct |
2 | Correct | 536 ms | 786432 KB | Output is correct |
3 | Correct | 327 ms | 786432 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 696 ms | 786432 KB | Output is correct |
2 | Execution timed out | 5099 ms | 786432 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 697 ms | 786432 KB | Output is correct |
2 | Execution timed out | 5117 ms | 786432 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 406 ms | 786432 KB | Output is correct |
2 | Execution timed out | 5081 ms | 786432 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |