# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
89214 | 2018-12-11T01:22:40 Z | jasony123123 | Sirni (COCI17_sirni) | C++11 | 5000 ms | 670448 KB |
#pragma GCC optimize ("O3") #pragma GCC target ("sse4") #define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #include <unordered_map> //#include <ext/pb_ds/tree_policy.hpp> //#include <ext/pb_ds/assoc_container.hpp> using namespace std; //using namespace __gnu_pbds; #define FOR(i,start,end) for(int i=start;i<(int)(end);i++) #define FORE(i,start,end) for(int i=start;i<=(int)end;i++) #define RFOR(i,start,end) for(int i = start; i>end; i--) #define RFORE(i,start,end) for(int i = start; i>=end; i--) #define all(a) a.begin(), a.end() #define mt make_tuple #define v vector #define sf scanf #define pf printf #define dvar(x) cout << #x << " := " << x << "\n" #define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n" typedef long long ll; typedef long double ld; typedef pair<int, int > pii; typedef pair<ll, ll> pll; //template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<class T> void minn(T &a, T b) { a = min(a, b); } template<class T> void maxx(T &a, T b) { a = max(a, b); } inline void io() { #ifdef LOCAL_PROJECT freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else /* online submission */ #endif ios_base::sync_with_stdio(false); cin.tie(NULL); } /**************************COCI 2016-2017 R6 P4*************************/ template <int SZ> struct UF { int N; // Vertices 0...N-1 int par[SZ], compsz[SZ]; // parent of i, size of component UF() { FOR(i, 0, SZ) par[i] = i, compsz[i] = 1; } int find(int x) { // path compression if (par[x] != x) par[x] = find(par[x]); return par[x]; } bool unite(int x, int y) { // unite by rank. return TRUE if united. FALSE if already same component x = find(x), y = find(y); if (x == y) return false; if (compsz[x] < compsz[y]) swap(x, y); // now x is the larger component compsz[x] += compsz[y]; par[y] = x; return true; } }; const int MAXP = 10000001; const int MAXN = 100001; const int thresh = 50000; int N; int M; int nxt[MAXP]; v<int> P; v<pii> edgeSorted[MAXP]; UF<MAXN> uf; void input() { // input sf("%d", &N); P.resize(N); FOR(i, 0, N) sf("%d", &P[i]); sort(P.begin(), P.end()); P.erase(unique(P.begin(), P.end()), P.end()); N = P.size(); M = P.back(); } void comNxt() { // compute nxt for (int i = M, j = P.size() - 1; i >= P.front(); i--) { if (j >= 0 && i == P[j]) nxt[i] = j--; else nxt[i] = nxt[i + 1]; } } void makeEd() { // compute edges pii e; int mod; FOR(i, 0, N) { e = { i, nxt[P[i] + 1] }; mod = P[e.second] % P[e.first]; if (mod<thresh) edgeSorted[mod].emplace_back(e); for (int k = P[i] + P[i]; k <= M; k += P[i]) { e = { i, nxt[k] }; mod = P[e.second] % P[e.first]; if(mod<thresh) edgeSorted[mod].emplace_back(e); } } } ll tree() { // mst int num = 0; ll mstcost = 0; FORE(c, 0, M) { for (pii e : edgeSorted[c]) { if (uf.unite(e.first, e.second)) { mstcost += (ll)(c); num++; } if (num == N - 1) { return mstcost; } } } assert(0); return mstcost; } int main() { io(); input(); comNxt(); makeEd(); pf("%lld\n", tree()); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 279 ms | 275200 KB | Output is correct |
2 | Correct | 814 ms | 304652 KB | Output is correct |
3 | Correct | 278 ms | 304652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 218 ms | 304652 KB | Output is correct |
2 | Correct | 3139 ms | 670448 KB | Output is correct |
3 | Correct | 305 ms | 670448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 298 ms | 670448 KB | Output is correct |
2 | Correct | 332 ms | 670448 KB | Output is correct |
3 | Correct | 271 ms | 670448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 284 ms | 670448 KB | Output is correct |
2 | Correct | 370 ms | 670448 KB | Output is correct |
3 | Correct | 295 ms | 670448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 225 ms | 670448 KB | Output is correct |
2 | Correct | 360 ms | 670448 KB | Output is correct |
3 | Correct | 272 ms | 670448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 417 ms | 670448 KB | Output is correct |
2 | Correct | 498 ms | 670448 KB | Output is correct |
3 | Correct | 345 ms | 670448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 258 ms | 670448 KB | Output is correct |
2 | Correct | 464 ms | 670448 KB | Output is correct |
3 | Correct | 309 ms | 670448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 460 ms | 670448 KB | Output is correct |
2 | Correct | 4863 ms | 670448 KB | Output is correct |
3 | Correct | 597 ms | 670448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 482 ms | 670448 KB | Output is correct |
2 | Execution timed out | 5154 ms | 670448 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 344 ms | 670448 KB | Output is correct |
2 | Execution timed out | 5123 ms | 670448 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |