結果
問題 | No.1477 Lamps on Graph |
ユーザー |
![]() |
提出日時 | 2021-04-16 22:12:08 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 1,863 bytes |
コンパイル時間 | 1,508 ms |
コンパイル使用メモリ | 33,536 KB |
実行使用メモリ | 8,320 KB |
最終ジャッジ日時 | 2024-07-03 02:02:49 |
合計ジャッジ時間 | 4,330 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 38 |
コンパイルメッセージ
main.c:60:1: warning: return type defaults to 'int' [-Wimplicit-int] 60 | main(){ | ^~~~ main.c: In function 'main': main.c:130:9: warning: implicit declaration of function 'write' [-Wimplicit-function-declaration] 130 | write(1,wbuf,wp-wbuf); | ^~~~~ main.c:131:9: warning: implicit declaration of function '_exit'; did you mean '_Exit'? [-Wimplicit-function-declaration] 131 | _exit(0); | ^~~~~ | _Exit
ソースコード
#pragma GCC optimize("Ofast")#pragma GCC target("avx2")char*mmap();#define rd(v) int v=0;{int _c;while(_c=*rp++-48,_c>=0)v=v*10+_c;}char wbuf[1<<28];#define WTHI(v) {long _z=v,_n=0,_d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(long*)wp=_d;wp+=_n;}#define WTLO(v) {long _z=v,_n=8,_d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(long*)wp=_d;wp+=8;}#define wt(v) WTHI(v)#define rep(v,e) for(int v=0;v<e;++v)#define MAXN 100000#define MAXM 100000int en[MAXN];int ei[MAXM];int eb[MAXM];int uv[MAXM<<1];int a[100000];char b[100000];typedef struct {int a,i;} S;S s[200000];void radix_sort_aux(S*a,S*b,int n){int c[256];for(int i=0;i<256;++i){c[i]=0;}for(int i=0;i<n;++i){++c[a[i].a&255];}int t=0;for(int i=0;i<256;++i){int u=c[i];c[i]=t;t+=u;}for(int i=0;i<n;++i){int j=c[a[i].a&255]++;unsigned aa=a[i].a;b[j].a=aa>>8|aa<<24;b[j].i=a[i].i;}}void radix_sort(S*a,int n){radix_sort_aux(a,a+n,n);radix_sort_aux(a+n,a,n);radix_sort_aux(a,a+n,n);radix_sort_aux(a+n,a,n);}main(){char*rp=mmap(0l,1l<<28,1,2,0,0ll);rd(n);rd(m);rep(i,n){rd(ai);a[i]=ai;s[i].a=ai;s[i].i=i;}radix_sort(s,n);int uvn=0;rep(i,m){rd(ui); --ui;rd(vi); --vi;if(a[ui]<a[vi]){uv[uvn++]=ui;uv[uvn++]=vi;++en[ui];}if(a[vi]<a[ui]){uv[uvn++]=vi;uv[uvn++]=ui;++en[vi];}}{int s=0;rep(i,n){ei[i]=s;s+=en[i];en[i]=0;}}for(int j=0;j<uvn;j+=2){int ui=uv[j+0];int vi=uv[j+1];eb[ei[ui]+en[ui]++]=vi;}rd(k);rep(i,k){rd(ki);b[ki-1]=1;}int c=0;char*wp=wbuf+8;rep(j,n){int i=s[j].i;if(b[i]){wt(i+1);*wp++=10;++c;rep(k,en[i]){b[eb[ei[i]+k]]^=1;}}}{char*wp=wbuf;wt(c);while(wp<wbuf+7){*wp++=32;}*wp++=10;}write(1,wbuf,wp-wbuf);_exit(0);}