Submission #496536


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=1000000000;
int n,m;
pair<int,pi> es[1000];

int largest[45];

int val[45];
int main(){
  cin>>n>>m;
  REP(i,m){
    cin>>es[i].sc.fr>>es[i].sc.sc>>es[i].fr;
    --es[i].sc.fr;
    --es[i].sc.sc;

    chmax(largest[es[i].sc.fr],es[i].fr);
    chmax(largest[es[i].sc.sc],es[i].fr);
  }

  sort(es,es+m);
  reverse(es,es+m);

  vector<int> root;
  REP(i,m){
    bool suc=true;
    int a=es[i].sc.fr,b=es[i].sc.sc;
    REP(j,i) if(es[j].sc.fr==a || es[j].sc.sc==a || es[j].sc.fr==b || es[j].sc.sc==b) suc=false;

    if(suc) root.pb(a);
  }


  int k=root.size();

  int res=0,ans[45];
  REP(bit,1<<k){
    REP(i,n) val[i]=INF;
    REP(i,k) if(bit>>i&1) val[root[i]]=largest[root[i]];

    int cnt=0;
    REP(i,m){
      int a=es[i].sc.fr,b=es[i].sc.sc;
      int c=es[i].fr;
      if((val[a]==INF)^(val[b]==INF)){
        if(val[a]==INF) val[a]=c;
        if(val[b]==INF) val[b]=c;
        ++cnt;
      }
    }
    if(res<cnt){
      res=cnt;
      memcpy(ans,val,sizeof(val));
    }
  }
  REP(i,n) printf("%d\n",ans[i]);

	return 0;
}

Submission Info

Submission Time
Task G - 天下一ゲーム
User hogloid
Language C++11 (GCC 4.9.2)
Score 220
Code Size 2056 Byte
Status
Exec Time 120 ms
Memory 1424 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 90 / 90 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt
Subtask2 130 / 130 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt
Case Name Status Exec Time Memory
sample_01.txt 35 ms 1244 KB
sample_02.txt 31 ms 1244 KB
sample_03.txt 31 ms 1240 KB
subtask1_01.txt 32 ms 1308 KB
subtask1_02.txt 31 ms 1300 KB
subtask1_03.txt 32 ms 1244 KB
subtask1_04.txt 30 ms 1308 KB
subtask1_05.txt 30 ms 1240 KB
subtask1_06.txt 32 ms 1312 KB
subtask1_07.txt 31 ms 1296 KB
subtask1_08.txt 32 ms 1292 KB
subtask1_09.txt 32 ms 1244 KB
subtask1_10.txt 30 ms 1312 KB
subtask1_11.txt 33 ms 1244 KB
subtask1_12.txt 31 ms 1328 KB
subtask1_13.txt 32 ms 1240 KB
subtask1_14.txt 30 ms 1244 KB
subtask1_15.txt 29 ms 1240 KB
subtask1_16.txt 31 ms 1308 KB
subtask1_17.txt 31 ms 1240 KB
subtask1_18.txt 33 ms 1244 KB
subtask1_19.txt 31 ms 1244 KB
subtask2_01.txt 34 ms 1244 KB
subtask2_02.txt 33 ms 1300 KB
subtask2_03.txt 32 ms 1244 KB
subtask2_04.txt 32 ms 1308 KB
subtask2_05.txt 34 ms 1300 KB
subtask2_06.txt 30 ms 1304 KB
subtask2_07.txt 32 ms 1296 KB
subtask2_08.txt 33 ms 1240 KB
subtask2_09.txt 33 ms 1296 KB
subtask2_10.txt 35 ms 1244 KB
subtask2_11.txt 31 ms 1240 KB
subtask2_12.txt 35 ms 1236 KB
subtask2_13.txt 33 ms 1300 KB
subtask2_14.txt 31 ms 1312 KB
subtask2_15.txt 33 ms 1308 KB
subtask2_16.txt 35 ms 1240 KB
subtask2_17.txt 36 ms 1296 KB
subtask2_18.txt 34 ms 1244 KB
subtask2_19.txt 49 ms 1308 KB
subtask2_20.txt 34 ms 1240 KB
subtask2_21.txt 54 ms 1276 KB
subtask2_22.txt 33 ms 1244 KB
subtask2_23.txt 48 ms 1240 KB
subtask2_24.txt 120 ms 1244 KB
subtask2_25.txt 35 ms 1244 KB
subtask2_26.txt 29 ms 1248 KB
subtask2_27.txt 32 ms 1248 KB
subtask2_28.txt 34 ms 1424 KB
subtask2_29.txt 38 ms 1308 KB
subtask2_30.txt 42 ms 1312 KB
subtask2_31.txt 33 ms 1304 KB
subtask2_32.txt 35 ms 1248 KB
subtask2_33.txt 39 ms 1300 KB
subtask2_34.txt 33 ms 1244 KB
subtask2_35.txt 34 ms 1244 KB
subtask2_36.txt 37 ms 1304 KB
subtask2_37.txt 34 ms 1244 KB
subtask2_38.txt 35 ms 1292 KB
subtask2_39.txt 31 ms 1248 KB