제출 #679621

#제출 시각아이디문제언어결과실행 시간메모리
679621as111Sirni (COCI17_sirni)C++14
98 / 140
5105 ms443396 KiB
#include <iostream> #include <vector> #include <set> #include <map> #include <algorithm> #include <queue> #define MAXN 100000 #define MAXP 10000000 using namespace std; typedef pair<int, int> pi; int parent[MAXN + 1]; // initialize parent[i] = i int findRoot(int a) { if (parent[a] == a) { return a; } return parent[a] = findRoot(parent[a]); } bool isConnected(int a, int b) { return findRoot(a) == findRoot(b); } // fastest method, check if 2 nodes are connected, check size of group int sz[MAXN + 1]; // initialize size[i] = 1 int depth[MAXN + 1]; // initialize depth[i] = 1 void join(int a, int b) { a = findRoot(a); b = findRoot(b); if (a == b) { return; } if (depth[a] < depth[b]) { parent[a] = b; sz[b] += sz[a]; } else { parent[b] = a; depth[a] = max(depth[a], depth[b] + 1); sz[a] += sz[b]; } } int N; int Cards[MAXN + 5]; set<int> cards; vector<pi> edges[MAXP + 5];; // PQ of edges priority_queue<pair<int, pi>> PQ; int card[MAXN + 5]; // value for each card ID map<int, int> ID; // card value to card ID int main() { cin >> N; for (int i = 0; i < N; i++) { cin >> Cards[i]; cards.insert(Cards[i]); } fill(depth, depth + MAXN + 1, 1); fill(sz, sz + MAXN + 1, 1); int i = 1; for (int c : cards) { ID[c] = i; card[i] = c; parent[i] = i; i++; } int mx = 0; for (int c : cards) { int mult = c; // multiple auto it = cards.upper_bound(mult); while (it != cards.end()) { if (*it - mult > c) mult += (*it - mult) / c * c; // c can be increased mx = max(mx, *it - mult); PQ.push({ -(*it - mult), {ID[c], ID[*it] } }); // negative weight to go from least to greatest //edges[*it - mult].push_back({ID[c], ID[*it]}); // negative weight to go from least to greatest mult += c; if (cards.count(mult)) { join(ID[c], ID[mult]); // multiple of c is a card, can join with no edge weight } it = cards.upper_bound(mult); } } int ans = 0; while (!PQ.empty()) { auto curr = PQ.top(); PQ.pop(); int w = -curr.first; int f = curr.second.first; int s = curr.second.second; if (!isConnected(f, s)) { join(f, s); ans += w; } } /* for (int p = 1; p <= mx;p++) { for (auto curr : edges[p]) { int f = curr.first; int s = curr.second; if (!isConnected(f, s)) { join(f, s); ans += p; } } }*/ cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...