結果

問題 No.556 仁義なきサルたち
コンテスト
ユーザー tsuishi
提出日時 2021-03-18 17:45:38
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 7,561 bytes
コンパイル時間 669 ms
コンパイル使用メモリ 33,920 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-16 21:03:05
合計ジャッジ時間 1,688 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
// Yukicoder №556 仁義なきサルたち ★★☆
// https://yukicoder.me/problems/no/556
// グループ人数つき Find tree
// ***********************
// for debug
#define DEBUGs
#define	YUKICODER
// -----------


#ifdef YUKICODER
#define gc(c)	do{c = getchar_unlocked();}while(0)
#define pc(c)	putchar_unlocked(c)
	extern char getchar_unlocked(void);
	extern void putchar_unlocked(char c);
#else
#define gc(c)	do{c = getchar();}while(0)
#define pc(c)	putchar(c)
#endif
void out(int n) { // 整数の表示（出力）
	int i;
	char b[30];

	if (!n) pc('0');
	else {
		if (n < 0) pc('-'), n = -n;
		i = 0; while (n) b[i++] = n % 10 + '0', n /= 10;
		while (i--) pc(b[i]);
	}
	pc('\n');
}
#define NOP do{}while(0)
#ifdef DEBUG
#define TRACE(...)	do{printf(__VA_ARGS__);fflush(stdout);}while(0)
#define TRACECR	do{putchar_unlocked('\n');fflush(stdout);}while(0)
#else
#define TRACE(...)	NOP
#define TRACECR	NOP
#endif
#define errmes(...)	do{fprintf(stderr,__VA_ARGS__);}while(0)
#define	mypc(d)	putchar_unlocked((int)(d))
#define PRINCR mypc('\n')
#define NOCR(strig)	do{char *p;p=strchr(strig,'\n');if(p)*p='\0';}while(0)
// for stdio
#define GETLINE(str)	do{char *p;fgets(str,sizeof(str),stdin);p=strchr(str,'\n');if(p)*p='\0';}while(0)
#define	GETINTS(a,b) {char s[34];int *ap=a;REP(i,b){GETWORD(s);*ap++=atoi(s);}}
#define SWAP(type,a,b)	do{type _c;_c=a;a=b;b=_c;}while(0)
#define MAX(a,b)	((a)>(b)?(a):(b))
#define REP(a,b) for(int a=0;a<(int)(b);++a)
#define REP1(a,b) for(int a=1;a<=(int)(b);++a)
#define Possible(a) 	   printf("%s",((a)?"Possible":"Impossible"))
#define possible(a) 	   printf("%s",((a)?"possible":"impossible"))
// The out-of-date function
#define	asctime(...)	asctime_s(...)
#define	ctime(...)		ctime_s(...)
#define	strlen(a)	mystr_len(a)
#define mystr_len(str)	mystr_len_lim(str,9999);
static char *GETWORD(char* str) {char c;char *cp;cp=&str[0];gc(c);while(c!=EOF){if((c==' ')||(c=='\n'))break;*cp++=c;gc(c);}*cp='\0';return &str[0];}
static int GETLINEINT(void) {char s[34];GETLINE(s);return atoi(s);}
static int GETWORDINT(void) {char s[34];GETWORD(s);return atoi(s);}
static long GETWORDLONG(void) {char s[34];GETWORD(s);return atol(s);}
static int maxi(int a,int b){if((a)>(b)){return a;}return b;}
static long maxl(long a,long b){if(a>b){return a;}return b;}
static int mystr_len_lim(char *str,int lim){int i=0;do{if(str[i]=='\0')break;i++;}while(i<lim);return i;}
// *********************
typedef struct DEFINT2 {
	int	x;
	int	y;
} TINT2;


// *********************
//	Union Find Tree
// ***********************
#define    MAXFRIEND	(10001)
#define    FRIENDNUMTYPE	int
FRIENDNUMTYPE	 Friend[MAXFRIEND];
int	Party[MAXFRIEND];

/*!
* @brief	   親の番号を返す
* @param[in]	me		本人の番号
* @return		親の番号、居ない時は自分の番号を返す
*/
int    whoparent( int num )
{
	int    saki;
	int    parent;
	int    frinum;

	TRACE("\nwhoparent(%d):",num);
	frinum = num;
	parent = Friend[ frinum ];
	if( parent < 0 ) {
		TRACE("parent is none. ret%d\n",frinum);
		return frinum;	  // 自分が根
	}
	while( (saki = Friend[ parent ]) >= 0 ) {	 // 親の親がある
		{
		TRACE("s%d ",saki);
		// 検索過程でついでにショートカットを作成しておく
		Friend[ parent ] = saki;	// 親の親に更新
		Friend[ frinum ] = saki;	// 親の親に更新
		TRACE("f%d=%d,",frinum,saki);
		frinum = parent;
		TRACE("p%d=%d ",parent,saki);
		}
		parent = saki;	  // 一つ親を注目点にする
	}
	if( saki < 0 ) {	// 根を発見
		frinum = parent;
	}
	Friend[ num ] = frinum;    // 当人だけショートカット
	TRACE("ret%d\n",frinum);
	return frinum;
}
// ***********************
/*!
* @brief	   親の番号を返す。その際とことんショートカット作成する。
* @param[in]	me		本人の番号
* @param[out]	nest	根までの深さを返す
* @return		親の番号、居ない時は自分の番号を返す
*/
// ***********************
int	wpstack[MAXFRIEND];
int	wpstackp = -1;
int    whoparent2( int num , int *nest)
{
	int    saki;
	int    parent;
	int    frinum;

	TRACE("\nwhoparent(%d):",num);
	frinum = num;
	*nest = 0;
	parent = Friend[ frinum ];
	if( parent < 0 ) {
		TRACE("parent is none. ret%d\n",frinum);
		return num;	  // 自分が根
	}
	wpstackp = -1;
	while( (saki = Friend[ parent ]) >= 0 ) {	 // 親の親がある
		wpstack[ ++wpstackp ] = parent;
		*nest++;
		parent = saki;	  // 一つ親を注目点にする
	}
	if( saki < 0 ) {	// 根を発見
		frinum = parent;
	}
	// 一部更新
	int	limit = 0;
	while( wpstackp >= 0 ) {
		Friend[ wpstack[ wpstackp-- ] ] = frinum;	 // ショートカット
		//if( ++limit > *nest/2 ) break;
	}
	TRACE("ret%d\n",frinum);
	return frinum;
}
// ***********************
/*!
* @brief	   根の番号を返す
* @param[in]	me		本人の番号
* @return		根の番号、居ない時は自分の番号を返す
*/
// ***********************
int    whoparent3( int num )
{
	if( Friend[ num ] < 0 ) {
		return num;	  // 自分が根
	}
	return Friend[ num ] = whoparent3( Friend[ num ] );
}
// ***********************
// 全く何もせずに親の番号を返す
int    whoparent4( int num )
{
	if( Friend[ num ] < 0 ) {
		return num;	  // 自分が根
	}
	return whoparent4( Friend[ num ] );
}
// ***********************
int    whoparent5( int num )
{
	if( Friend[ num ] < 0 ) {
		return num;	  // 自分が根
	}
	Friend[ num ] = whoparent4( num ); // 自分だけショートカット
	return Friend[ num ];
}
// ***********************
/*!
* @brief	   友人リンクを作成する
* @param[in]	fri   友人の番号。
* @param[in]	me		本人の番号
* @return		失敗したら-1を返す。
*/
int    addfriend( int fri, int me )
{
	int    a_fri,b_fri;
	int    a_pare,b_pare;

	TRACE("add(%d,%d) ",fri,me);
	if( fri == me ) return 0;	 // 同じ場合。
	a_fri = fri;
	b_fri = me;
	a_pare = whoparent3( a_fri );
	b_pare = whoparent3( b_fri );
	if( a_pare > b_pare ) {
		SWAP(FRIENDNUMTYPE,a_pare,b_pare);	  // 根の若番をaにする
		SWAP(FRIENDNUMTYPE,a_fri,b_fri);	  // 根の若番をaにする
	}
	TRACE("parent(%d>%d[%d],%d>%d[%d]) ",a_fri,a_pare,Party[a_pare],b_fri,b_pare,Party[b_pare]);
	if( a_pare == b_pare ) {
		TRACE("already.\n");
		return 0;	 // 既に友人
	} else if( Party[a_pare] < Party[b_pare] ) {
		TRACE("set %d>%d\n",a_pare,b_pare);
		Friend[ a_pare ] = b_pare;
		Party[ b_pare ] += Party[ a_pare ];
		// Party[ a_pare ] = 0;		// 速度向上の為省略可
	} else if( Party[a_pare] >= Party[b_pare] ){
		TRACE("set %d>%d\n",b_pare,a_pare);
		Friend[ b_pare ] = a_pare;
		Party[ a_pare ] += Party[ b_pare ];
		// Party[ b_pare ] = 0;		// 速度向上の為省略可
	}
	return 0;
}
// ***********************
/*!
* @brief	   友人か確認する
* @param[in]	fri1   友人かもしれない番号。
* @param[in]	fri2   本人の番号
* @return		友人なら1を返す。
*/
int    checkfriend( int fri1, int fri2 ) {
	if( whoparent3( fri1 ) == whoparent3( fri2 ) ) {
		return 1;
	} else {
		return 0;
	}
}
// ***********************
void Init_friend( int max ) {
	int    i;

	for( i = 0 ; i <= max ; i++ ) {
		Friend[i] = -1;
		Party[i] = 1;
	}
}
// *********************
// *********************
// *********************
int main( void ) {
	int	N,M;
	int	a,b;

	N = GETWORDINT();
	M = GETWORDINT();

	Init_friend( N );

	REP1(i,M) {
		a = GETWORDINT();
		b = GETWORDINT();
		addfriend( a, b );
	}
	

	TRACE("\n --- readed --- \n");
	// --------
	REP1(i,N) {
		out( whoparent3(i) );
	}
}
0