結果

問題 No.416 旅行会社
ユーザー tsuishitsuishi
提出日時 2021-03-11 14:58:53
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 8,439 bytes
コンパイル時間 337 ms
コンパイル使用メモリ 33,920 KB
実行使用メモリ 15,232 KB
最終ジャッジ日時 2024-10-13 03:33:43
合計ジャッジ時間 11,500 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'GETWORD':
main.c:31:21: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
   31 | #define mygc(c) (c)=getchar_unlocked()
      |                     ^~~~~~~~~~~~~~~~
main.c:32:61: note: in expansion of macro 'mygc'
   32 | 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];}
      |                                                             ^~~~

ソースコード

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
// -----------

#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"))

// *********************
int	q1[200001];
int	q2[200001];
int	q3[200001];
int	q4[200001];
int	br1[200001];
int	br2[200001];
// *********************
//  Union Find Tree
// ***********************
#define    MAXFRIEND    (100001)
#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 frinum;    // 自分が根
    }
	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 > 50 ) break;
	}
    TRACE("ret%d\n",frinum);
    return frinum;
}
// ***********************
/*!
* @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_fri,b_fri;
    int    a_pare,b_pare;
    int		n1,n2;

    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 = whoparent2( a_fri , &n1 );
    b_pare = whoparent2( b_fri , &n2 );
    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( n1 < n2 ) {
        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]    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;
	}
}
// *********************
int main( void ) {
	int	N,M,Q;
	int	qs;
	int	par;

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

	REP1(i,M) {
		br1[i] = GETWORDINT();
		br2[i] = GETWORDINT();
	}
	REP1(i,Q) {
		q1[i] = GETWORDINT();
		q2[i] = GETWORDINT();
	}
	// 壊れている状態を作る
	memcpy( &q3[1] , &q1[1] , sizeof(int)*Q );
	memcpy( &q4[1] , &q2[1] , sizeof(int)*Q );
	REP1(i,M) {
		int	flg = 0;
		TRACE("check(%d,%d)\n",br1[i],br2[i] );
		REP1(h,qs) TRACE("(%d,%d)",q3[h],q4[h]);TRACECR;
		for(int k = 1; k <= qs ; k++ ) {
			if(( br1[i] == q3[k] )&&( br2[i] == q4[k] )) {
				flg = 1;
				if( qs > k ) { q3[k] = q3[qs];  q4[k] = q4[qs]; }	qs--;
				REP1(h,qs) TRACE("(%d,%d)",q3[h],q4[h]);TRACECR;
				break;
			}
		}
		if( !(flg) ) {
			addfriend2( br1[i], br2[i] );
		}
	}
	TRACE(" --- all broken --- \n");
	par = whoparent( 1 );
	for( int i = 2; i <= N; i++) {
		if( whoparent( i ) == par ) {
			// 最初から到達できている
			broken[i] = -1;
		}
	}
	for( int i = Q ; i > 0 ; --i ) {
		TRACE(" --- %d --- \n",i);
		addfriend2( q1[i] , q2[i] );
		par = whoparent( 1 );
		for(int k=2; k<=N ; k++ ) {
			if( broken[k] == 0 ) {
				// まだ到達できていない
				if( whoparent( k ) == par ) {
					// 修復した
					broken[k] = i;
					TRACE("arrival%d.time%d\n",k,i);
				}
			}
		}
	}
	// --------
	for(int k=2; k<=N ; k++ ) {
		printf("%d\n",broken[k]);
	}
}
0