Submission #00088

ソースコード

?
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<bits/stdc++.h>
using namespace std;
// Main data
int h,w,n,q;
int X1[302],X2[302],Y1[302],Y2[302];
int sx[1000002],sy[1000002],gx[1000002],gy[1000002];
int id[2000][2000];
int h_r[2000] , w_r[2000];
// Function_Zip
vector<int>vx,vy;
int Zip_x() , Zip_y();
// Main
int main(){
// Init
for(int i=0;i<2000;i++)for(int j=0;j<2000;j++)id[i][j] = 0;
// Input
scanf(" %d %d %d %d",&h,&w,&n,&q);
for(int i=0;i<n;i++)scanf(" %d %d %d %d",&X1[i],&Y1[i],&X2[i],&Y2[i]);
for(int i=0;i<q;i++)scanf(" %d %d %d %d",&sx[i],&sy[i],&gx[i],&gy[i]);
// Zip
h = Zip_y(); w = Zip_x();
// Fill Wall == '-1'
for(int cc=0;cc<n;cc++)for(int i=Y1[cc];i<=Y2[cc];i++)for(int j=X1[cc];j<=X2[cc];j++)id[i][j] = -1;
// BFS
int dh[4] = {0,1,0,-1};
int dw[4] = {1,0,-1,0};
int now_id = 0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(id[i][j] != 0)continue;
now_id++; id[i][j] = now_id;
queue<pair<int,int> >que; que.push( make_pair(i,j) );
while(!que.empty()){
pair<int,int> f = que.front(); que.pop();
for(int cc=0;cc<4;cc++){
int nh=f.first+dh[cc] , nw=f.second+dw[cc];
if(nh<0 || h<=nh || nw<0 || w<=nw)continue;
if(id[nh][nw] != 0)continue;
id[nh][nw] = now_id;
que.push( make_pair(nh,nw) );
}
}
}
}
// Solve Query
for(int i=0;i<q;i++){
// Binary Search
int nsy=0,nsx=0,ngy=0,ngx=0;
// sy
int left = 0 , right = h-1 , mid;
while(left<=right){
mid = (left+right)/2;
if(h_r[mid] <= sy[i]){nsy = mid;left=mid+1;}
else right=mid-1;
}
// sx
left = 0 , right = w-1;
while(left<=right){
mid = (left+right)/2;
if(w_r[mid] <= sx[i]){nsx = mid;left=mid+1;}
else right=mid-1;
}
// gy
left = 0 , right = h-1;
while(left<=right){
mid = (left+right)/2;
if(h_r[mid] <= gy[i]){ngy = mid;left=mid+1;}
else right=mid-1;
}
// gx
left = 0 , right = w-1;
while(left<=right){
mid = (left+right)/2;
if(w_r[mid] <= gx[i]){ngx = mid;left=mid+1;}
else right=mid-1;
}
// Output
if(id[nsy][nsx]==id[ngy][ngx] && id[nsy][nsx]!=-1){
printf("Success\n");
}
else{
printf("Broadcasting accident\n");
}
}
return(0);
}
int Zip_x(){
// Push x data
for(int i=0;i<n;i++){
for(int d=-1;d<=1;d++){
int tx1=X1[i]+d , tx2=X2[i]+d;
if(0<=tx1 && tx1<w)vx.push_back(tx1);
if(0<=tx2 && tx2<w)vx.push_back(tx2);
}
}
// Sort
vx.push_back(0);vx.push_back(w-1);
sort(vx.begin(),vx.end());
// Erase Overlap data
vx.erase(unique(vx.begin(),vx.end()),vx.end());
// Set w_r
for(int i=0;i<vx.size();i++)w_r[i] = vx[i];
// Set new array_x
for(int i=0;i<n;i++){
X1[i] = find(vx.begin(),vx.end(),X1[i])-vx.begin();
X2[i] = find(vx.begin(),vx.end(),X2[i])-vx.begin();
}
return(vx.size());
}
int Zip_y(){
// Push y data
for(int i=0;i<n;i++){
for(int d=-1;d<=1;d++){
int ty1=Y1[i]+d , ty2=Y2[i]+d;
if(0<=ty1 && ty1<h)vy.push_back(ty1);
if(0<=ty2 && ty2<h)vy.push_back(ty2);
}
}
// Sort
vy.push_back(0);vy.push_back(h-1);
sort(vy.begin(),vy.end());
// Erase Overlap data
vy.erase(unique(vy.begin(),vy.end()),vy.end());
// Set h_r
for(int i=0;i<vy.size();i++)h_r[i] = vy[i];
// Set new array_y
for(int i=0;i<n;i++){
Y1[i] = find(vy.begin(),vy.end(),Y1[i])-vy.begin();
Y2[i] = find(vy.begin(),vy.end(),Y2[i])-vy.begin();
}
return(vy.size());
}

ステータス

項目 データ
問題 0005 - 回れ雛月花 -Lunatic
ユーザー名 root
投稿日時 2017-12-22 15:30:45
言語 C++11
状態 Accepted
得点 350
ソースコード長 3753 Byte
最大実行時間 421 ms
最大メモリ使用量 104268 KB

セット

セット 得点 Cases
1 Burn 35 / 35 Input0* , Input10
2 Out 140 / 140 Input[0-2]* , Input30
3 Misfortune 175 / 175 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
Input01 AC 18 ms 23008 KB
1
2
3
Input02 AC 23 ms 22992 KB
1
2
3
Input03 AC 26 ms 22980 KB
1
2
3
Input04 AC 25 ms 22972 KB
1
2
3
Input05 AC 17 ms 22952 KB
1
2
3
Input06 AC 28 ms 23072 KB
1
2
3
Input07 AC 19 ms 23056 KB
1
2
3
Input08 AC 17 ms 16900 KB
1
2
3
Input09 AC 20 ms 23160 KB
1
2
3
Input10 AC 22 ms 23140 KB
1
2
3
Input11 AC 40 ms 23128 KB
2
3
Input12 AC 21 ms 22952 KB
2
3
Input13 AC 37 ms 23060 KB
2
3
Input14 AC 22 ms 23008 KB
2
3
Input15 AC 42 ms 23116 KB
2
3
Input16 AC 30 ms 16932 KB
2
3
Input17 AC 36 ms 23180 KB
2
3
Input18 AC 21 ms 23008 KB
2
3
Input19 AC 36 ms 23248 KB
2
3
Input20 AC 24 ms 23076 KB
2
3
Input21 AC 23 ms 23060 KB
2
3
Input22 AC 19 ms 23040 KB
2
3
Input23 AC 23 ms 23280 KB
2
3
Input24 AC 23 ms 23124 KB
2
3
Input25 AC 22 ms 23240 KB
2
3
Input26 AC 35 ms 23100 KB
2
3
Input27 AC 44 ms 23192 KB
2
3
Input28 AC 27 ms 23140 KB
2
3
Input29 AC 38 ms 17092 KB
2
3
Input30 AC 24 ms 23192 KB
2
3
Input31 AC 26 ms 23292 KB
3
Input32 AC 37 ms 23520 KB
3
Input33 AC 40 ms 23352 KB
3
Input34 AC 60 ms 23684 KB
3
Input35 AC 24 ms 23764 KB
3
Input36 AC 33 ms 24004 KB
3
Input37 AC 55 ms 24236 KB
3
Input38 AC 48 ms 24192 KB
3
Input39 AC 32 ms 24308 KB
3
Input40 AC 32 ms 24412 KB
3
Input41 AC 401 ms 39740 KB
3
Input42 AC 416 ms 47068 KB
3
Input43 AC 405 ms 54076 KB
3
Input44 AC 408 ms 61384 KB
3
Input45 AC 410 ms 68520 KB
3
Input46 AC 410 ms 75560 KB
3
Input47 AC 419 ms 82764 KB
3
Input48 AC 421 ms 89764 KB
3
Input49 AC 415 ms 97192 KB
3
Input50 AC 405 ms 104268 KB
3