# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
46347 | 2018-04-19T17:01:59 Z | evpipis | Sirni (COCI17_sirni) | C++ | 760 ms | 373480 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); cnt[temp] = 1; } 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]; if (cnt[i+1]) nex[1][i] = i+1; if (cnt[i]) cnt[i] = ++k; } 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 | Incorrect | 293 ms | 281720 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 196 ms | 281720 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 290 ms | 282472 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 299 ms | 282472 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 242 ms | 282472 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 665 ms | 282472 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 269 ms | 282472 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 760 ms | 368180 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 641 ms | 373480 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 372 ms | 373480 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |