Submission #2060028
Source Code Expand
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #define NDEBUG #include "cout11.h" #endif #undef NDEBUG #include <cassert> typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> ii; typedef pair<ll,ll> llll; typedef pair<double,double> dd; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ii> vii; typedef vector<vector<ii>> vvii; typedef vector<ll> vll; #define sz(a) int((a).size()) #define pb push_back #define FOR(var,from,to) for(int var=(from);var<=(to);++var) #define rep(var,n) for(int var=0;var<(n);++var) #define rep1(var,n) for(int var=1;var<=(n);++var) #define repC2(vari,varj,n) for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj) #define ALL(c) (c).begin(),(c).end() #define RALL(c) (c).rbegin(),(c).rend() #define tr(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i) #define found(s,e) ((s).find(e)!=(s).end()) #define mset(arr,val) memset(arr,val,sizeof(arr)) #define mid(x,y) ((x)+((y)-(x))/2) #define IN(x,a,b) ((a)<=(x)&&(x)<=(b)) #define INTSPACE 12 char _buf[INTSPACE*1000000 + 3]; int loadint() { if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0; return atoi(_buf); } int loadvec(vector<int>& v, int N=-1) { if (N == -1) { N = loadint(); if (N==0) return 0; } int bufsize = INTSPACE*N + 3; if (fgets(_buf, bufsize, stdin)==NULL) return 0; v.resize(N); int i=0; bool last = false; for (char *p=&_buf[0]; ;) { char *q = p; while (*q > ' ') ++q; if (*q == 0x0D || *q == 0x0A) last = true; *q = 0; v[i++] = atoi(p); if (last || i == N) break; p = q+1; } // assert(i <= N); return i; } class UnionFind { vector<int> data; public: UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; int Z; vvi Q; ll solve(){ int Z = Q.size(); if (Z == 1) return 0; int consume = (Q.size() - 1) * 2; ll cost = 0; int rest = 0; priority_queue<int> pq; rep(i, Z) { cost += Q[i][0]; --consume; int y = Q[i].size(); rest += y - 1; for (int j=1; j<y; ++j) { pq.push(-Q[i][j]); } } if (consume > rest) return -1; rep(i, consume) { cost += -pq.top(); pq.pop(); } return cost; } int main() { vector<int> tmp(2); loadvec(tmp, 2); int N=tmp[0], M=tmp[1]; vector<int> a(N); loadvec(a, N); UnionFind uf(N); rep(i, M) { loadvec(tmp, 2); int x=tmp[0], y=tmp[1]; uf.unionSet(x,y); } map<int,vi> ms; rep(i, N){ ms[uf.root(i)].pb(a[i]); } for (auto p:ms){ sort(ALL(p.second)); Q.pb(p.second); } // sort(ALL(Q)); ll ans = solve(); if (ans < 0) { cout << "Impossible" << endl; } else { cout << ans << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Forest |
User | naoya_t |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 3370 Byte |
Status | AC |
Exec Time | 52 ms |
Memory | 19508 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 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 | AC | 1 ms | 256 KB |
1_004.txt | AC | 51 ms | 19124 KB |
1_005.txt | AC | 46 ms | 19252 KB |
1_006.txt | AC | 40 ms | 18868 KB |
1_007.txt | AC | 42 ms | 18096 KB |
1_008.txt | AC | 46 ms | 17332 KB |
1_009.txt | AC | 51 ms | 10804 KB |
1_010.txt | AC | 42 ms | 8628 KB |
1_011.txt | AC | 37 ms | 7348 KB |
1_012.txt | AC | 26 ms | 3700 KB |
1_013.txt | AC | 26 ms | 3700 KB |
1_014.txt | AC | 25 ms | 3320 KB |
1_015.txt | AC | 49 ms | 18352 KB |
1_016.txt | AC | 44 ms | 18352 KB |
1_017.txt | AC | 43 ms | 19508 KB |
1_018.txt | AC | 42 ms | 19124 KB |
1_019.txt | AC | 45 ms | 18100 KB |
1_020.txt | AC | 51 ms | 10932 KB |
1_021.txt | AC | 42 ms | 8628 KB |
1_022.txt | AC | 36 ms | 7476 KB |
1_023.txt | AC | 26 ms | 3696 KB |
1_024.txt | AC | 26 ms | 3696 KB |
1_025.txt | AC | 25 ms | 3320 KB |
1_026.txt | AC | 21 ms | 8632 KB |
1_027.txt | AC | 19 ms | 8632 KB |
1_028.txt | AC | 18 ms | 8628 KB |
1_029.txt | AC | 18 ms | 8628 KB |
1_030.txt | AC | 21 ms | 7992 KB |
1_031.txt | AC | 22 ms | 5048 KB |
1_032.txt | AC | 17 ms | 3900 KB |
1_033.txt | AC | 15 ms | 3388 KB |
1_034.txt | AC | 10 ms | 1596 KB |
1_035.txt | AC | 10 ms | 1596 KB |
1_036.txt | AC | 10 ms | 1404 KB |
1_037.txt | AC | 47 ms | 17584 KB |
1_038.txt | AC | 41 ms | 17584 KB |
1_039.txt | AC | 39 ms | 17584 KB |
1_040.txt | AC | 40 ms | 17456 KB |
1_041.txt | AC | 48 ms | 17332 KB |
1_042.txt | AC | 47 ms | 10164 KB |
1_043.txt | AC | 37 ms | 7860 KB |
1_044.txt | AC | 31 ms | 6708 KB |
1_045.txt | AC | 20 ms | 2928 KB |
1_046.txt | AC | 20 ms | 2928 KB |
1_047.txt | AC | 19 ms | 2552 KB |
1_048.txt | AC | 47 ms | 10932 KB |
1_049.txt | AC | 52 ms | 10932 KB |
1_050.txt | AC | 47 ms | 10932 KB |
1_051.txt | AC | 51 ms | 10932 KB |