oj.uz

Submission #949048

# Submission time Handle Problem Language Result Execution time Memory
949048 2024-03-18T21:01:58 Z Saul0906 Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 139268 KB 
#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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory 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

Subtask #2
0 / 12.0

# Verdict Execution time Memory 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 -

Subtask #3
0 / 24.0

# Verdict Execution time Memory 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 -

Subtask #4
0 / 27.0

# Verdict Execution time Memory 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 -

Subtask #5
0 / 26.0

# Verdict Execution time Memory 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 -