Submission #13554
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include<bits/stdc++.h> using namespace std; typedef pair< int , int >pint; typedef vector< int >vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template < class T, class U> void chmin(T &t,U f){ if (t>f)t=f;} template < class T, class U> void chmax(T &t,U f){ if (t<f)t=f;} int dy[]={-1,0,1,0}; int dx[]={0,-1,0,1}; int H,W; char fld[333][333]; int orig,dest; vint G[111111]; vint T[111111]; int dep[111111]; int par[20][111111]; int topmost[111111]; void dfs( int v, int p, int d){ dep[v]=d; par[0][v]=p; topmost[v]=dep[v]; for (auto u:G[v]){ if (u==p) continue ; if (dep[u]==-1){ dfs(u,v,d+1); T[v].pb(u); chmin(topmost[v],topmost[u]); } else { chmin(topmost[v],dep[u]); } } } int lca( int u, int v){ if (dep[u]<dep[v])swap(u,v); rep(i,20) if ((dep[u]-dep[v])>>i&1)u=par[i][u]; if (u==v) return u; for ( int i=19;i>=0;i--) if (par[i][u]!=par[i][v])u=par[i][u],v=par[i][v]; return par[0][u]; } int longest[111111]; void dfs2( int v, int p){ if (p!=-1)longest[v]=longest[p]; if (dep[v]-1>topmost[v])longest[v]++; for (auto u:T[v]) if (u!=p)dfs2(u,v); } signed main(){ int orig,dest; scanf ( "%d%d" ,&H,&W); rep(i,H) scanf ( "%s" ,fld[i]); rep(i,H)rep(j,W){ if (fld[i][j]== 'S' )orig=i*W+j; if (fld[i][j]== 'G' )dest=i*W+j; if (fld[i][j]== '#' ) continue ; rep(d,4){ int ny=i+dy[d],nx=j+dx[d]; if (ny<0||ny>=H||nx<0||nx>=W||fld[ny][nx]== '#' ) continue ; G[i*W+j].pb(ny*W+nx); } } memset (dep,-1, sizeof (dep)); dfs(orig,-1,0);dfs2(orig,-1); //rep(i,H*W)if(dep[i]==-1)dfs(i,-1,0); //rep(i,H*W)if(dep[i]==0)dfs2(i,-1); rep(i,19)rep(j,H*W){ if (par[i][j]==-1)par[i+1][j]=-1; else par[i+1][j]=par[i][par[i][j]]; } int Q;Q=1; //scanf("%d",&Q); while (Q--){ /*int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); a--;b--;c--;d--; int v=a*W+b; int u=c*W+d; */ int v=orig,u=dest; if (dep[v]>dep[u])swap(v,u); int p=lca(v,u); bool ok; if (v==p){ if (dep[u]-dep[p]-1>longest[u])ok= true ; else ok= false ; } else { if (dep[v]-dep[p]>longest[v]||dep[u]-dep[p]>longest[u])ok= true ; else ok= false ; } puts (ok? "yes" : "no" ); } return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 0650 - メロンパン |
ユーザー名 | latte0119 |
投稿日時 | 2017-03-12 03:42:47 |
言語 | C++11 |
状態 | Accepted |
得点 | 15 |
ソースコード長 | 2764 Byte |
最大実行時間 | 31 ms |
最大メモリ使用量 | 15612 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 15 / 15 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
01_sample1.txt | AC | 28 ms | 13664 KB |
1
|
01_sample2.txt | AC | 21 ms | 13656 KB |
1
|
01_sample3.txt | AC | 20 ms | 13648 KB |
1
|
02_random1.txt | AC | 24 ms | 13644 KB |
1
|
02_random2.txt | AC | 29 ms | 13628 KB |
1
|
02_random3.txt | AC | 15 ms | 13620 KB |
1
|
02_random4.txt | AC | 23 ms | 13744 KB |
1
|
02_random5.txt | AC | 18 ms | 13868 KB |
1
|
02_random6.txt | AC | 18 ms | 13732 KB |
1
|
02_random7.txt | AC | 21 ms | 13728 KB |
1
|
02_random8.txt | AC | 22 ms | 13596 KB |
1
|
02_random9.txt | AC | 19 ms | 13720 KB |
1
|
02_random10.txt | AC | 15 ms | 13636 KB |
1
|
03_random1.txt | AC | 19 ms | 13840 KB |
1
|
03_random2.txt | AC | 15 ms | 13772 KB |
1
|
03_random3.txt | AC | 19 ms | 13820 KB |
1
|
03_random4.txt | AC | 31 ms | 13872 KB |
1
|
03_random5.txt | AC | 21 ms | 13888 KB |
1
|
03_random6.txt | AC | 22 ms | 13684 KB |
1
|
04_ei1331.txt | AC | 21 ms | 13716 KB |
1
|
04_ei1332.txt | AC | 18 ms | 13832 KB |
1
|
04_ei1333.txt | AC | 16 ms | 13952 KB |
1
|
04_ei1334.txt | AC | 25 ms | 15612 KB |
1
|
04_ei1335.txt | AC | 21 ms | 15604 KB |
1
|
05_random1.txt | AC | 19 ms | 14472 KB |
1
|
05_random2.txt | AC | 19 ms | 14292 KB |
1
|
05_random3.txt | AC | 17 ms | 14208 KB |
1
|
05_random4.txt | AC | 22 ms | 14236 KB |
1
|
05_random5.txt | AC | 19 ms | 14300 KB |
1
|
05_random6.txt | AC | 28 ms | 14388 KB |
1
|
06_handmake1.txt | AC | 14 ms | 13856 KB |
1
|