fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <vector>
  3. #define ll long long
  4. #define ld long double
  5.  
  6.  
  7. using namespace std;
  8. const ld PI=3.141592654;
  9.  
  10. ld sq(ld a) {return a*a;}
  11. ld dist(ld a, ld b, ld x, ld y) {return sqrtl(sq((x-a))+sq(y-b));}
  12.  
  13.  
  14.  
  15. vector<set<ll>> adj;
  16. vector<bool>vis;
  17. ll c=0;
  18. void dfs(ll x){
  19.     vis[x]=1;
  20.     c++;
  21.     for(auto ch:adj[x]){
  22.         if(!vis[ch]){
  23.             dfs(ch);
  24.         }
  25.     }
  26. }
  27.  
  28.     vector<ll>ans;
  29. ll dp(ll ind,ll m1,ll m2,ll c){
  30.     if(ind==ans.size()){
  31.         return c;
  32.     }
  33.     ll ch1=1e15,ch2=1e15,ch3=1e15;
  34.     if(ans[ind]<=m1){
  35.         ch1=dp(ind+1,m1-ans[ind],m2,c);
  36.     }
  37.     if(ans[ind]<=m2){
  38.         ch2=dp(ind+1,m1,m2-ans[ind],c);
  39.     }
  40.     ch3=dp(ind+1,m1,m2,c+=ans[ind]);
  41.     return min({ch1,ch2,ch3});
  42. }
  43.  
  44.  
  45.  
  46.  
  47. void solve(){
  48.     ll n,m1,m2;
  49.     cin >> n >> m1 >> m2;
  50.     map<string,ll>mp;
  51.     vis.assign(2*n+10,0);
  52.     ll i=1;
  53.     adj.assign(2*n+10,{});
  54.     for(ll j=0;j<n;j++){
  55.         string a,b;
  56.         cin >> a >>b;
  57.         if(mp[a]==0){
  58.             mp[a]=i;
  59.             i++;
  60.         }
  61.         if(mp[b]==0){
  62.             mp[b]=i;
  63.             i++;
  64.         }
  65.         adj[mp[a]].insert(mp[b]);
  66.         adj[mp[b]].insert(mp[a]);
  67.     }
  68.     for(ll l=1;l<i;l++){
  69.         if(!vis[l]){
  70.             c=0;
  71.             dfs(l);
  72.             ans.push_back(c);
  73.         }
  74.     }
  75.     cout << dp(0,m1,m2,0);
  76. }
  77.  
  78. int main(){
  79.     freopen("land.in","r",stdin);
  80.     ll t=1;
  81.     cin >> t;
  82.     while(t--){
  83.         solve();
  84.     }
  85. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mqwwiF
language:
C++ (gcc 8.3)
created:
2 days 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!