#include <bits/stdc++.h>
#include "rainbow.h"
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a: b)
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
using namespace std;
set<pii> river;
set<int> rows[200005], cols[200005];
vector<pii> nriver;
void init(int R, int C, int sr, int sc, int M, char *S){
river.clear();
nriver.clear();
river.insert({sr,sc});
rep(i,0,2e5+5){
cols[i].clear();
rows[i].clear();
cols[i].insert(0);
cols[i].insert(R+1);
rows[i].insert(0);
rows[i].insert(C+1);
}
rep(i,0,M){
nriver.pb({sr+1,sc});
nriver.pb({sr-1,sc});
nriver.pb({sr,sc+1});
nriver.pb({sr,sc-1});
rows[sr].insert(sc);
cols[sc].insert(sr);
if(S[i]=='N') sr--;
else if(S[i]=='S') sr++;
else if(S[i]=='W') sc--;
else sc++;
river.insert({sr,sc});
}
nriver.pb({sr+1,sc});
nriver.pb({sr-1,sc});
nriver.pb({sr,sc+1});
nriver.pb({sr,sc-1});
rows[sr].insert(sc);
cols[sc].insert(sr);
}
set<pii> vis;
map<pii,pii> dsu;
pii find(pii a){
if(!dsu.count(a) || dsu[a]==a) return a;
return dsu[a]=find(dsu[a]);
}
void join(pii a, pii b){
dsu[find(a)]=find(b);
}
void dfs(int x, int y, int ar, int ac, int br, int bc){
if(x<ar || x>br || y<ac || y>bc) return;
vis.insert({x,y});
join({x,y},{x,y});
auto it=rows[x].lower_bound(y);
int y1, y2, x1, x2;
y2=*it;
it--;
y1=*it;
it=cols[y].lower_bound(x);
x2=*it;
it--;
x1=*it;
y1=max(y1,ac-1)+1;
y2=min(y2,bc+1)-1;
x1=max(x1,ar-1)+1;
x2=min(x2,br+1)-1;
{join({x,y},{x,y1}); if(!vis.count({x,y1})) dfs(x,y1,ar,ac,br,bc);}
{join({x,y},{x,y2}); if(!vis.count({x,y2})) dfs(x,y2,ar,ac,br,bc);}
{join({x,y},{x1,y}); if(!vis.count({x1,y})) dfs(x1,y,ar,ac,br,bc);}
{join({x,y},{x2,y}); if(!vis.count({x2,y})) dfs(x2,y,ar,ac,br,bc);}
}
int colour(int ar, int ac, int br, int bc){
vis.clear();
dsu.clear();
int c=0;
nriver.pb({ar,ac});
nriver.pb({br,bc});
vector<pii> ext;
repa(e,nriver) if(!river.count(e) && !vis.count(e)){
ext.pb({e.fi+1,e.se});
ext.pb({e.fi-1,e.se});
ext.pb({e.fi,e.se+1});
ext.pb({e.fi,e.se-1});
}
repa(e,nriver) if(!river.count(e) && !vis.count(e)) dfs(e.fi,e.se,ar,ac,br,bc);
repa(e,ext) if(!river.count(e) && !vis.count(e)) dfs(e.fi,e.se,ar,ac,br,bc);
nriver.pop_back();
nriver.pop_back();
repa(e,dsu) if(e.fi==e.se) c++;
//, cout<<e.fi.fi<<" "<<e.fi.se<<endl;
return c;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
283 ms |
57096 KB |
Output is correct |
2 |
Correct |
1495 ms |
57400 KB |
Output is correct |
3 |
Correct |
342 ms |
56916 KB |
Output is correct |
4 |
Correct |
466 ms |
57168 KB |
Output is correct |
5 |
Correct |
1680 ms |
57480 KB |
Output is correct |
6 |
Correct |
46 ms |
56656 KB |
Output is correct |
7 |
Correct |
47 ms |
56660 KB |
Output is correct |
8 |
Correct |
47 ms |
56660 KB |
Output is correct |
9 |
Correct |
47 ms |
56668 KB |
Output is correct |
10 |
Correct |
50 ms |
56656 KB |
Output is correct |
11 |
Correct |
759 ms |
57212 KB |
Output is correct |
12 |
Correct |
989 ms |
57172 KB |
Output is correct |
13 |
Correct |
1700 ms |
57316 KB |
Output is correct |
14 |
Correct |
2160 ms |
57732 KB |
Output is correct |
15 |
Correct |
53 ms |
56656 KB |
Output is correct |
16 |
Correct |
49 ms |
56772 KB |
Output is correct |
17 |
Correct |
53 ms |
56656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
56772 KB |
Output is correct |
2 |
Correct |
53 ms |
56656 KB |
Output is correct |
3 |
Execution timed out |
3023 ms |
80464 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
53 ms |
56656 KB |
Output is correct |
2 |
Correct |
1980 ms |
116344 KB |
Output is correct |
3 |
Correct |
1533 ms |
114008 KB |
Output is correct |
4 |
Correct |
2191 ms |
127084 KB |
Output is correct |
5 |
Correct |
1111 ms |
101968 KB |
Output is correct |
6 |
Correct |
127 ms |
65204 KB |
Output is correct |
7 |
Correct |
238 ms |
71328 KB |
Output is correct |
8 |
Correct |
374 ms |
85440 KB |
Output is correct |
9 |
Correct |
251 ms |
81980 KB |
Output is correct |
10 |
Correct |
145 ms |
64708 KB |
Output is correct |
11 |
Correct |
192 ms |
76608 KB |
Output is correct |
12 |
Correct |
227 ms |
83000 KB |
Output is correct |
13 |
Correct |
249 ms |
83000 KB |
Output is correct |
14 |
Correct |
211 ms |
83136 KB |
Output is correct |
15 |
Correct |
197 ms |
80184 KB |
Output is correct |
16 |
Correct |
107 ms |
63676 KB |
Output is correct |
17 |
Correct |
170 ms |
71348 KB |
Output is correct |
18 |
Correct |
201 ms |
83048 KB |
Output is correct |
19 |
Correct |
1445 ms |
108140 KB |
Output is correct |
20 |
Correct |
2543 ms |
135212 KB |
Output is correct |
21 |
Correct |
674 ms |
97692 KB |
Output is correct |
22 |
Correct |
657 ms |
94664 KB |
Output is correct |
23 |
Correct |
176 ms |
65344 KB |
Output is correct |
24 |
Correct |
795 ms |
95524 KB |
Output is correct |
25 |
Execution timed out |
3074 ms |
139268 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
283 ms |
57096 KB |
Output is correct |
2 |
Correct |
1495 ms |
57400 KB |
Output is correct |
3 |
Correct |
342 ms |
56916 KB |
Output is correct |
4 |
Correct |
466 ms |
57168 KB |
Output is correct |
5 |
Correct |
1680 ms |
57480 KB |
Output is correct |
6 |
Correct |
46 ms |
56656 KB |
Output is correct |
7 |
Correct |
47 ms |
56660 KB |
Output is correct |
8 |
Correct |
47 ms |
56660 KB |
Output is correct |
9 |
Correct |
47 ms |
56668 KB |
Output is correct |
10 |
Correct |
50 ms |
56656 KB |
Output is correct |
11 |
Correct |
759 ms |
57212 KB |
Output is correct |
12 |
Correct |
989 ms |
57172 KB |
Output is correct |
13 |
Correct |
1700 ms |
57316 KB |
Output is correct |
14 |
Correct |
2160 ms |
57732 KB |
Output is correct |
15 |
Correct |
53 ms |
56656 KB |
Output is correct |
16 |
Correct |
49 ms |
56772 KB |
Output is correct |
17 |
Correct |
53 ms |
56656 KB |
Output is correct |
18 |
Execution timed out |
3023 ms |
86464 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
283 ms |
57096 KB |
Output is correct |
2 |
Correct |
1495 ms |
57400 KB |
Output is correct |
3 |
Correct |
342 ms |
56916 KB |
Output is correct |
4 |
Correct |
466 ms |
57168 KB |
Output is correct |
5 |
Correct |
1680 ms |
57480 KB |
Output is correct |
6 |
Correct |
46 ms |
56656 KB |
Output is correct |
7 |
Correct |
47 ms |
56660 KB |
Output is correct |
8 |
Correct |
47 ms |
56660 KB |
Output is correct |
9 |
Correct |
47 ms |
56668 KB |
Output is correct |
10 |
Correct |
50 ms |
56656 KB |
Output is correct |
11 |
Correct |
759 ms |
57212 KB |
Output is correct |
12 |
Correct |
989 ms |
57172 KB |
Output is correct |
13 |
Correct |
1700 ms |
57316 KB |
Output is correct |
14 |
Correct |
2160 ms |
57732 KB |
Output is correct |
15 |
Correct |
53 ms |
56656 KB |
Output is correct |
16 |
Correct |
49 ms |
56772 KB |
Output is correct |
17 |
Correct |
53 ms |
56656 KB |
Output is correct |
18 |
Execution timed out |
3023 ms |
86464 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |