Submission #3050774
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, a[N]; vector<int> g[N]; vector<int> vals; bool vis[N]; void dfs(int u) { if (vis[u]) return; vis[u] = 1; vals.push_back(a[u]); for (auto v : g[u]) dfs(v); } int main() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i]; int iter = m; while (iter--) { int u,v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } if (n == 1) return cout << 0, 0; bool good = n >= 2*(n-m-1); if (!good) return cout << "Impossible\n", 0; vector<int> rest; int deg = 2*(n-m-1); long long ans = 0; for (int u = 0; u < n; u++) if (!vis[u]) { vals.clear(); dfs(u); sort(vals.begin(), vals.end(), greater<int>()); ans += vals.back(); vals.pop_back(); deg--; for (auto x : vals) rest.push_back(x); } sort(rest.begin(), rest.end(), greater<int>()); while (deg--) { ans += rest.back(); rest.pop_back(); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Forest |
User | aurinegro |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1143 Byte |
Status | RE |
Exec Time | 228 ms |
Memory | 7420 KB |
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 | 2 ms | 2560 KB |
0_001.txt | AC | 2 ms | 2560 KB |
0_002.txt | AC | 2 ms | 2560 KB |
1_003.txt | AC | 2 ms | 2560 KB |
1_004.txt | AC | 41 ms | 2944 KB |
1_005.txt | AC | 42 ms | 2944 KB |
1_006.txt | AC | 41 ms | 2944 KB |
1_007.txt | AC | 42 ms | 3072 KB |
1_008.txt | AC | 50 ms | 3584 KB |
1_009.txt | AC | 85 ms | 5504 KB |
1_010.txt | AC | 100 ms | 6268 KB |
1_011.txt | AC | 106 ms | 6524 KB |
1_012.txt | AC | 131 ms | 7416 KB |
1_013.txt | AC | 125 ms | 7416 KB |
1_014.txt | RE | 228 ms | 7412 KB |
1_015.txt | AC | 42 ms | 2944 KB |
1_016.txt | AC | 42 ms | 2944 KB |
1_017.txt | AC | 42 ms | 2944 KB |
1_018.txt | AC | 42 ms | 3072 KB |
1_019.txt | AC | 49 ms | 3584 KB |
1_020.txt | AC | 85 ms | 5504 KB |
1_021.txt | AC | 99 ms | 6268 KB |
1_022.txt | AC | 107 ms | 6524 KB |
1_023.txt | AC | 130 ms | 7416 KB |
1_024.txt | AC | 126 ms | 7420 KB |
1_025.txt | RE | 218 ms | 7420 KB |
1_026.txt | AC | 10 ms | 2816 KB |
1_027.txt | AC | 10 ms | 2816 KB |
1_028.txt | AC | 10 ms | 2816 KB |
1_029.txt | AC | 10 ms | 2816 KB |
1_030.txt | AC | 13 ms | 3072 KB |
1_031.txt | AC | 29 ms | 3968 KB |
1_032.txt | AC | 35 ms | 4352 KB |
1_033.txt | AC | 38 ms | 4608 KB |
1_034.txt | AC | 48 ms | 4988 KB |
1_035.txt | AC | 47 ms | 4988 KB |
1_036.txt | RE | 141 ms | 4988 KB |
1_037.txt | AC | 18 ms | 2944 KB |
1_038.txt | AC | 18 ms | 2944 KB |
1_039.txt | AC | 19 ms | 2944 KB |
1_040.txt | AC | 18 ms | 3072 KB |
1_041.txt | AC | 32 ms | 3584 KB |
1_042.txt | AC | 59 ms | 5504 KB |
1_043.txt | AC | 73 ms | 6392 KB |
1_044.txt | AC | 80 ms | 6524 KB |
1_045.txt | AC | 99 ms | 7416 KB |
1_046.txt | AC | 99 ms | 7420 KB |
1_047.txt | RE | 193 ms | 7420 KB |
1_048.txt | AC | 78 ms | 4992 KB |
1_049.txt | AC | 86 ms | 5504 KB |
1_050.txt | AC | 77 ms | 4992 KB |
1_051.txt | AC | 85 ms | 5520 KB |