fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define s second
  4. #define f first
  5. typedef long long ll;
  6. typedef pair<ll,pair<ll,ll> > pii;
  7. ll a[2000005];
  8. ll get(ll x){
  9.     if(a[x]==x)return x;
  10.     return a[x]=get(a[x]);
  11. }
  12. void join(ll x,ll y){
  13.     a[get(x)]=a[get(y)];
  14. }
  15. int main(){
  16.     ll n,mm,k;
  17.     cin>>n>>mm>>k;
  18.     map<int,int>m;
  19.     for(ll i=1;i<=k;i++){
  20.         ll x;
  21.         cin>>x;
  22.         m[i]=x;
  23.     }
  24.     for(ll i=1;i<=n;i++)a[i]=i;
  25.     vector<pii>v,res;
  26.     while(mm--){
  27.         ll s=0;
  28.         ll u,vv,l;
  29.         cin>>u>>vv>>l;
  30.         while(l--){
  31.             ll x;
  32.             cin>>x;
  33.             s|=(1<<(x));
  34.         }
  35.         v.push_back({s,{u,vv}});
  36.     }
  37.     sort(v.begin(),v.end());
  38.     ll sum=0;
  39.     for(ll i=0;i<v.size();i++){
  40.         pii it=v[i];
  41.         if(a[get(it.s.f)]!=a[get(it.s.s)]){
  42.             join(it.s.f,it.s.s);
  43.             res.push_back(it);
  44.             sum|=it.f;
  45.         }
  46.     }
  47.     if(res.size()!=(n-1))cout<<-1<<endl;
  48.     else {ll aa=0;
  49.     for(ll i=1;i<=k;i++)if(sum&(1<<i))aa+=m[i];
  50.         cout<<aa<<endl;
  51.     }
  52.  
  53. }
Time limit exceeded #stdin #stdout 5s 808196KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jlQljY
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!