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