結果
| 問題 |
No.416 旅行会社
|
| コンテスト | |
| ユーザー |
 tsuishi
|
| 提出日時 | 2021-03-11 14:11:42 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,237 bytes |
| コンパイル時間 | 1,908 ms |
| コンパイル使用メモリ | 33,516 KB |
| 実行使用メモリ | 20,424 KB |
| 最終ジャッジ日時 | 2024-10-13 02:41:25 |
| 合計ジャッジ時間 | 12,088 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 1 -- * 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];}
| ^~~~
ソースコード
#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] 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] 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) ) {
addfriend( 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);
addfriend( 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]);
}
}