Submission #486406


Source Code Expand

Copy
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
	template<class S,class T>
	ostream &operator <<(ostream& out,const pair<S,T>& a){
		out<<'('<<a.fr<<','<<a.sc<<')';
		return out;
	}
}

const int INF=5e8;
struct uf{

	static const int MAXN=105;
	int par[MAXN];
	int size[MAXN];

  vector<int> mxi[MAXN];
	void init(){
		memset(par,-1,sizeof(par));
		REP(i,MAXN) size[i]=1;
	}
	int root(int a){
		if(par[a]==-1) return a;
		return par[a]=root(par[a]);
	}
	void unite(int a,int b){
		a=root(a);b=root(b);
		if(a==b) return;
		if(size[a]<size[b]) swap(a,b);

		par[b]=a;
		size[a]+=size[b];
	}
	bool same(int a,int b){
		return root(a)==root(b);
	}
};


int n,m,k;
pi es[5000];
int g[105][105];

int dist[105];
 

uf u;
int id[105];
int main(){
  u.init();
  cin>>n>>m>>k;
  REP(i,m){
    cin>>es[i].fr>>es[i].sc;
    g[es[i].fr][es[i].sc]=g[es[i].sc][es[i].fr]=1;
    u.unite(es[i].fr,es[i].sc);
  }

  REP(i,n) id[i]=u.root(i);

  if(1){
    REP(i,(1<<n)) if(__builtin_popcount(i)==k){
      bool fail=false;
      REP(j,m) if((i>>es[j].fr&1) && (i>>es[j].sc&1)){
        fail=true;
        break;
      }
      if(!fail){
        REP(j,n) if(i>>j&1) printf("%d\n",j);
        return 0;
      }
    }
  }else{
    REP(i,n){
      REP(j,n) dist[j]=INF;
      dist[i]=0;
      queue<int> q;q.push(i);
      while(!q.empty()){
        int cur=q.front();q.pop();
        REP(j,n) if(dist[j]==INF && g[cur][j]){
          dist[j]=dist[cur]+1;
          q.push(j);
        }
      }
      int cnt=0,flag=0;

      REP(j,n) if(dist[j]%2==0 && dist[j]<INF) ++cnt;



      int t=id[i];
      int sz=u.size[t];
      if(cnt*2<sz) cnt=sz-cnt,flag=1;

      if(u.mxi[t].size()<cnt){
        u.mxi[t].clear();
        REP(j,n) if(dist[j]%2==flag && dist[j]<INF)  u.mxi[t].pb(j);
      }
    }

    vector<int> res;
    REP(i,n) if(id[i]==i){
      for(auto a:u.mxi[i]) res.pb(a);
    }
    sort(ALL(res));
    if(res.size()<k) return 0;
    REP(i,k) printf("%d\n",res[i]);
  }
	return 0;
}

Submission Info

Submission Time
Task B - B 問題
User hogloid
Language C++11 (GCC 4.9.2)
Score 12
Code Size 2842 Byte
Status
Exec Time 29 ms
Memory 932 KB

Judge Result

Set Name Score / Max Score Test Cases
All 10 / 10 00_sample_1.txt, 00_sample_2.txt, 00_sample_3.txt, 20_random_1.txt, 20_random_10.txt, 20_random_11.txt, 20_random_12.txt, 20_random_13.txt, 20_random_14.txt, 20_random_15.txt, 20_random_16.txt, 20_random_17.txt, 20_random_18.txt, 20_random_19.txt, 20_random_2.txt, 20_random_20.txt, 20_random_21.txt, 20_random_22.txt, 20_random_23.txt, 20_random_24.txt, 20_random_25.txt, 20_random_26.txt, 20_random_27.txt, 20_random_28.txt, 20_random_29.txt, 20_random_3.txt, 20_random_30.txt, 20_random_4.txt, 20_random_5.txt, 20_random_6.txt, 20_random_7.txt, 20_random_8.txt, 20_random_9.txt
asi1024 0 / 2 31_asi1024.txt
atetubou 0 / 2 32_atetubou.txt
climpet 0 / 2 33_climpet.txt
DEGwer 0 / 2 34_DEGwer.txt
evima 0 / 2 35_evima.txt
flowlight 0 / 2 36_flowlight.txt
hogloid 0 / 2 37_hogloid.txt
ichyo 0 / 2 38_ichyo.txt
math 0 / 2 39_math.txt
miki_im 0 / 2 40_miki_im.txt
natsugiri 0 / 2 41_natsugiri.txt
piroz95 0 / 2 42_piroz95.txt
semiexp 0 / 2 43_semiexp.txt
sigma425 2 / 2 44_sigma425.txt
sky58 0 / 2 45_sky58.txt
snuke 0 / 2 46_snuke.txt
tozangezan 0 / 2 47_tozangezan.txt
wo01 0 / 2 48_wo01.txt
yosupo 0 / 2 49_yosupo.txt
zerokugi 0 / 2 50_zerokugi.txt
Case Name Status Exec Time Memory
00_sample_1.txt 24 ms 800 KB
00_sample_2.txt 24 ms 916 KB
00_sample_3.txt 24 ms 928 KB
20_random_1.txt 25 ms 932 KB
20_random_10.txt 24 ms 924 KB
20_random_11.txt 25 ms 932 KB
20_random_12.txt 23 ms 728 KB
20_random_13.txt 25 ms 928 KB
20_random_14.txt 25 ms 932 KB
20_random_15.txt 23 ms 928 KB
20_random_16.txt 25 ms 736 KB
20_random_17.txt 25 ms 928 KB
20_random_18.txt 25 ms 800 KB
20_random_19.txt 24 ms 924 KB
20_random_2.txt 25 ms 928 KB
20_random_20.txt 23 ms 924 KB
20_random_21.txt 25 ms 804 KB
20_random_22.txt 25 ms 800 KB
20_random_23.txt 28 ms 796 KB
20_random_24.txt 23 ms 928 KB
20_random_25.txt 24 ms 924 KB
20_random_26.txt 25 ms 800 KB
20_random_27.txt 25 ms 924 KB
20_random_28.txt 25 ms 796 KB
20_random_29.txt 25 ms 924 KB
20_random_3.txt 25 ms 916 KB
20_random_30.txt 29 ms 736 KB
20_random_4.txt 26 ms 804 KB
20_random_5.txt 23 ms 932 KB
20_random_6.txt 25 ms 928 KB
20_random_7.txt 25 ms 932 KB
20_random_8.txt 25 ms 928 KB
20_random_9.txt 24 ms 796 KB
31_asi1024.txt 26 ms 928 KB
32_atetubou.txt 23 ms 844 KB
33_climpet.txt 23 ms 932 KB
34_DEGwer.txt 26 ms 920 KB
35_evima.txt 25 ms 928 KB
36_flowlight.txt 27 ms 880 KB
37_hogloid.txt 23 ms 924 KB
38_ichyo.txt 23 ms 796 KB
39_math.txt 25 ms 924 KB
40_miki_im.txt 25 ms 804 KB
41_natsugiri.txt 27 ms 932 KB
42_piroz95.txt 26 ms 796 KB
43_semiexp.txt 25 ms 892 KB
44_sigma425.txt 25 ms 924 KB
45_sky58.txt 25 ms 916 KB
46_snuke.txt 27 ms 924 KB
47_tozangezan.txt 26 ms 924 KB
48_wo01.txt 26 ms 920 KB
49_yosupo.txt 25 ms 796 KB
50_zerokugi.txt 25 ms 924 KB