結果

問題 No.416 旅行会社
ユーザー tsuishitsuishi
提出日時 2021-03-15 11:30:40
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 10,650 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 36,224 KB
実行使用メモリ 14,616 KB
最終ジャッジ日時 2024-11-07 00:14:36
合計ジャッジ時間 19,449 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3,922 ms
14,616 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 4 ms
6,820 KB
testcase_09 AC 53 ms
6,816 KB
testcase_10 AC 3,834 ms
7,740 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
// Yukicoder №416 旅行会社 Easy ★★★
// https://yukicoder.me/problems/no/416
// ***********************
// for debug
#define DEBUGs
// -----------
#if 1
#define gc() getchar_unlocked()
#define pc(c) putchar_unlocked(c)
#else
#define gc() getchar()
#define pc(c) putchar(c)
#endif
extern char getchar_unlocked(void);
extern void putchar_unlocked(char c);

int in() {	// 非負整数の入力
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

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	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)
// The out-of-date function
#define	asctime(...)	asctime_s(...)
#define	ctime(...)		ctime_s(...)
#define	strlen(a)	mystr_len(a)

// for stdio
#define GETLINE(str) do{char *p;fgets(str,sizeof(str),stdin);p=strchr(str,'\n');if(p)*p='\0';}while(0)
#define mygc(c) (c)=getchar_unlocked()
static char *GETWORD(char* str) {char c;char *cp;cp=&str[0];mygc(c);while(c!=EOF){if((c==' ')||(c=='\n'))break;*cp++=c;mygc(c);}*cp='\0';return &str[0];}
#define	GETINTS(a,b) {char s[34];int *ap=a;REP(i,b){GETWORD(s);*ap++=atoi(s);}}
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;}
#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"))

// *********************
typedef struct DEFINT2 {
	int	x;
	int	y;
} TINT2;

TINT2	q[200002];
TINT2	qx[200002];
TINT2	br[200002];

// *********************
//	Union Find Tree
// ***********************
#define    MAXFRIEND	(100002)
#define    FRIENDNUMTYPE	int
FRIENDNUMTYPE	 Friend[MAXFRIEND];
int	broken[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;
	//if( a_fri < b_fri ) SWAP(FRIENDNUMTYPE,a_fri,b_fri);	  // なるべく若番を親にする
	a_pare = whoparent( a_fri );
	b_pare = whoparent( b_fri );
	TRACE("parent(%d>%d,%d>%d) ",a_fri,a_pare,b_fri,b_pare);
	if( a_pare == b_pare ) {
		TRACE("already.\n");
		return 0;	 // 既に友人
	} else if( a_pare > b_pare ) {
		TRACE("set %d>%d\n",a_pare,b_pare);
		Friend[ a_pare ] = b_pare;	  // 若い方の親に新しい親を付ける
	} else {
		TRACE("set %d>%d\n",b_pare,a_pare);
		Friend[ b_pare ] = a_pare;	  // 若い方の親に新しい親を付ける
	}
	return 0;
}
// ***********************
/*!
* @brief	   友人リンクを作成する(軽量版)
* @param[in]	fri   友人の番号。
* @param[in]	me		本人の番号
* @return		失敗したら-1を返す。
*/
int    addfriend2( int fri, int me )
{
	int    a_pare,b_pare;
	int		n1,n2;
	int		dmy;

	TRACE("add(%d,%d) ",fri,me);
	if( fri == me ) return 0;	 // 同じ場合。
	//if( a_fri < b_fri ) SWAP(FRIENDNUMTYPE,a_fri,b_fri);	  // なるべく若番を親にする
	a_pare = whoparent2( fri , &n1 );
	b_pare = whoparent2( me , &n2 );
	TRACE("parent(%d>%d,%d>%d) ",fri,a_pare,me,b_pare);
	if( a_pare == b_pare ) {
		TRACE("already.\n");
		return 0;	 // 既に友人
	} else if( n1 < n2 ) {
		TRACE("set %d>%d\n",a_pare,b_pare);
		Friend[ a_pare ] = b_pare;	  // 枝が少ない親に新しい親を付ける
		//whoparent2( fri , &dmy);
	} else {
		TRACE("set %d>%d\n",b_pare,a_pare);
		Friend[ b_pare ] = a_pare;	  // 枝が少ない親に新しい親を付ける
		//whoparent2( me , &dmy);
	}
	return 0;
}
// ***********************
/*!
* @brief	   友人か確認する
* @param[in]	fri1   友人かもしれない番号。
* @param[in]	fri2   本人の番号
* @return		友人なら1を返す。
*/
int    checkfriend( int fri1, int fri2 ) {
	if( whoparent( fri1 ) == whoparent( fri2 ) ) {
		return 1;
	} else {
		return 0;
	}
}
// ***********************
void Init_friend( int max ) {
	int    i;

	for( i = 0 ; i <= max ; i++ ) {
		Friend[i] = -1;
	}
	for( i = 0 ; i < MAXFRIEND ; ++i ) {
		broken[i] = 0;
	}
}
// *********************
extern	int cmpINT2(const void * n1, const void * n2) {
	int  a, b;
	TINT2	*np1, *np2;
	np1 = (TINT2 *)n1;
	np2 = (TINT2 *)n2;
	a = np1->x;
	b = np2->x;
	if( a == b ) {
		a = np1->y;
		b = np2->y;
	}
#if 0
	// 1 is 降順 5 4 3 2 1
	if( a > b ) return -1;
	else if( a < b ) return 1;
	else return 0;
#else
	// 0 is 昇順 1 2 3 4 5
	if( a < b ) return -1;
	else if( a > b ) return 1;
	else return 0;
#endif
}
// *********************
int	ptsstack[MAXFRIEND+5];
int	ptsstackp = -1;
inline int ptspop(void) {
	return ptsstack[ ptsstackp-- ];
}
inline void ptspush(int	a) {
	ptsstack[ ++ptsstackp ] = a;
}
inline void ptsinit(void) {
	ptsstackp = -1;
}
inline void ptsdelete(int idx) {
	TRACE("idx id %d\n",idx);
	ptsstack[idx] = ptsstack[ ptsstackp-- ];
}
// *********************
int main( void ) {
	int	N,M,Q;
	int	qs;
	int	par;
	int	bidx;
	int	kidx;
	int	xr,yr;
	int dmy;

	N = GETWORDINT();
	M = GETWORDINT();
	Q = GETWORDINT();
	qs = Q;
	Init_friend( N );

	REP1(i,M) {
		br[i].x = GETWORDINT();
		br[i].y = GETWORDINT();
	}
	REP1(i,Q) {
		q[i].x = GETWORDINT();
		q[i].y = GETWORDINT();
	}
	// 壊れている状態を作る
	memcpy( &qx[1] , &q[1] , sizeof( qx[0] )*Q );
	qsort( &br[1], M , sizeof( br[1] ) , cmpINT2 );
	qsort( &qx[1], Q , sizeof( qx[1] ) , cmpINT2 );
	bidx = 1;
	REP1(i,Q) {
		TRACE("check(%d,%d)\n",qx[i].x,qx[i].y );
		while( qx[i].x > br[bidx].x ) if( ++bidx > M ) break;
		if( bidx > M ) break;
		while( qx[i].y > br[bidx].y ) if( ++bidx > M ) break;
		if( i > M ) break;
		br[bidx].x = -1;
	}
	TRACE("bredge make ");
	REP1(i,M) if( br[i].x >= 0 ) {
		TRACE("(%d,%d)", br[i].x, br[i].y );
		addfriend2( br[i].x, br[i].y );
	}
	

	TRACE("\n --- all broken --- \n");
	ptsinit();
	par = whoparent3( 1 );
	for( int i = 2; i <= N; i++) {
		if( whoparent3( i ) == par ) {
			// 最初から到達できている
			broken[i] = -1;
		} else {
			ptspush( i );
		}
	}
	REP(k,1) {
		for( int i = 2; i <= N; i++) {
			whoparent2( i ,&dmy);	// ショートカット作成のため呼び出す
			//whoparent3( i );	// ショートカット作成のため呼び出す
		}
	}
	par = whoparent5( 1 );
	for( int i = Q ; i > 0 ; --i ) {
		if( i %1000 == 0 ) fprintf(stderr,"%d,",i); 
		//par = whoparent2( 1 , &dmy );
		xr = whoparent5( q[i].x  );
		yr = whoparent5( q[i].y  );
		addfriend( q[i].x , q[i].y );
		if(( xr != par )&&( yr != par )) continue;
		if(( xr == par )&&( yr == par )) continue;
		par = whoparent5( 1 );
		kidx = 0;
		while( kidx <= ptsstackp  ) {
			bidx = ptsstack[kidx];	// まだ到達できていないリスト
			if( whoparent5( bidx ) == par ) {
				// 修復した
				broken[bidx] = i;
				TRACE("arrival%d.time%d\n",bidx,i);
				ptsstack[ kidx ] = ptsstack[ ptsstackp-- ];
			} else {
				kidx++;
			}
		}
	}
	// --------
	for(int k=2; k<=N ; k++ ) {
		out(broken[k]);
	}
}
0