Submission #3046198
Source Code Expand
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <vector> #include <queue> #include <stack> #include <algorithm> #include <map> #include <set> #include <cmath> #include <stdlib.h> #include <functional> #define ll long long #define llu unsigned long long #define INF 0x3f3f3f3f #define LINF 0x3f3f3f3f3f3f3f3f using namespace std; const int N = 1e5 + 10; int n, m; ll cost[N]; bool vis[N]; vector<pair<ll, int>> vec; vector<vector<pair<ll, int>>> L; vector<int> vt; int P[N]; int _find(int x) { return P[x] = (P[x] != x ? _find(P[x]) : x); } void merge(int x, int y) { P[_find(y)] = _find(x); } int newidx(int x) { return lower_bound(vt.begin(), vt.end(), x) - vt.begin(); } int main() { int i, j, k, x, y; scanf("%d%d", &n, &m); for (i = 0; i < n; ++i) { scanf("%lld", &cost[i]); P[i] = i; vec.push_back({ cost[i], i }); } sort(vec.begin(), vec.end()); for (i = 0; i < m; ++i) { scanf("%d%d", &x, &y); merge(x, y); } for (i = 0; i < n; ++i) { vt.push_back(_find(i)); } sort(vt.begin(), vt.end()); vt.erase(unique(vt.begin(), vt.end()), vt.end()); L.resize(vt.size()); for (i = 0; i < n; ++i) { L[newidx(_find(i))].push_back({ cost[i], i }); } for (i = 0; i < L.size(); ++i) sort(L[i].begin(), L[i].end()); ll sum = 0; int cnt = L.size(); if (n < 2 * (L.size() - 1)) { printf("Impossible\n"); return 0; } if (cnt == 1) { printf("0\n"); return 0; } for (i = 0; i < L.size(); ++i) { vis[L[i][0].second] = true; sum += L[i][0].first; } if (cnt == L.size()) { printf("%lld\n", sum); return 0; } int lim = 2*L.size() - 2; for (i = 0; i < vec.size(); ++i) { if (!vis[vec[i].second]) { sum += vec[i].first; cnt++; if (cnt >= lim) break; } } printf("%lld\n", sum); }
Submission Info
Submission Time | |
---|---|
Task | D - Forest |
User | kiimak |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1896 Byte |
Status | WA |
Exec Time | 56 ms |
Memory | 9328 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:43:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &n, &m); ^ ./Main.cpp:46:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld", &cost[i]); ^ ./Main.cpp:54:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &x, &y); ^
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 600 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 1 ms | 256 KB |
0_001.txt | AC | 1 ms | 256 KB |
0_002.txt | AC | 1 ms | 256 KB |
1_003.txt | WA | 1 ms | 256 KB |
1_004.txt | AC | 35 ms | 8816 KB |
1_005.txt | AC | 34 ms | 8816 KB |
1_006.txt | AC | 36 ms | 8816 KB |
1_007.txt | AC | 38 ms | 8688 KB |
1_008.txt | AC | 40 ms | 8432 KB |
1_009.txt | WA | 54 ms | 7152 KB |
1_010.txt | WA | 51 ms | 6512 KB |
1_011.txt | WA | 52 ms | 6384 KB |
1_012.txt | WA | 53 ms | 7280 KB |
1_013.txt | WA | 53 ms | 7280 KB |
1_014.txt | AC | 52 ms | 6896 KB |
1_015.txt | AC | 35 ms | 8816 KB |
1_016.txt | AC | 38 ms | 8816 KB |
1_017.txt | AC | 36 ms | 8816 KB |
1_018.txt | AC | 38 ms | 8816 KB |
1_019.txt | AC | 40 ms | 8432 KB |
1_020.txt | WA | 54 ms | 7280 KB |
1_021.txt | WA | 53 ms | 6512 KB |
1_022.txt | WA | 52 ms | 6384 KB |
1_023.txt | WA | 54 ms | 7280 KB |
1_024.txt | WA | 53 ms | 7280 KB |
1_025.txt | AC | 53 ms | 7024 KB |
1_026.txt | AC | 16 ms | 4468 KB |
1_027.txt | AC | 16 ms | 4468 KB |
1_028.txt | AC | 17 ms | 4468 KB |
1_029.txt | AC | 18 ms | 4340 KB |
1_030.txt | AC | 18 ms | 4212 KB |
1_031.txt | WA | 24 ms | 3700 KB |
1_032.txt | WA | 24 ms | 3316 KB |
1_033.txt | WA | 24 ms | 3188 KB |
1_034.txt | WA | 25 ms | 3700 KB |
1_035.txt | WA | 25 ms | 3700 KB |
1_036.txt | AC | 25 ms | 3572 KB |
1_037.txt | AC | 32 ms | 8816 KB |
1_038.txt | AC | 33 ms | 8816 KB |
1_039.txt | AC | 33 ms | 9328 KB |
1_040.txt | AC | 34 ms | 8816 KB |
1_041.txt | AC | 37 ms | 8432 KB |
1_042.txt | WA | 52 ms | 7280 KB |
1_043.txt | WA | 51 ms | 6512 KB |
1_044.txt | WA | 51 ms | 6384 KB |
1_045.txt | WA | 52 ms | 7280 KB |
1_046.txt | WA | 53 ms | 7280 KB |
1_047.txt | AC | 52 ms | 7024 KB |
1_048.txt | AC | 54 ms | 7152 KB |
1_049.txt | WA | 54 ms | 7280 KB |
1_050.txt | AC | 54 ms | 7152 KB |
1_051.txt | WA | 56 ms | 7280 KB |