oj.uz

Submission #949027

# Submission time Handle Problem Language Result Execution time Memory
949027 2024-03-18T20:03:27 Z Saul0906 Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 133208 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;
	if(!river.count({x,y1})) join({x,y},{x,y1});
	if(!river.count({x,y2})) join({x,y},{x,y2});
	if(!river.count({x1,y})) join({x,y},{x1,y});
	if(!river.count({x2,y})) join({x,y},{x2,y});
	if(!river.count({x,y1}) && !vis.count({x,y1})) dfs(x,y1,ar,ac,br,bc);
	if(!river.count({x,y2}) && !vis.count({x,y2})) dfs(x,y2,ar,ac,br,bc);
	if(!river.count({x1,y}) && !vis.count({x1,y})) dfs(x1,y,ar,ac,br,bc);
	if(!river.count({x2,y}) && !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 288 ms 56656 KB Output is correct
2 Correct 1595 ms 57208 KB Output is correct
3 Correct 374 ms 56916 KB Output is correct
4 Correct 500 ms 56916 KB Output is correct
5 Correct 1742 ms 57660 KB Output is correct
6 Correct 57 ms 56700 KB Output is correct
7 Correct 49 ms 56748 KB Output is correct
8 Correct 50 ms 56660 KB Output is correct
9 Correct 50 ms 56660 KB Output is correct
10 Correct 56 ms 56656 KB Output is correct
11 Correct 802 ms 57168 KB Output is correct
12 Correct 1036 ms 57172 KB Output is correct
13 Correct 1761 ms 57352 KB Output is correct
14 Correct 2191 ms 57984 KB Output is correct
15 Correct 55 ms 56996 KB Output is correct
16 Correct 53 ms 56656 KB Output is correct
17 Correct 51 ms 56652 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 56656 KB Output is correct
2 Correct 51 ms 56652 KB Output is correct
3 Execution timed out 3017 ms 79072 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 56996 KB Output is correct
2 Correct 2125 ms 118680 KB Output is correct
3 Correct 1833 ms 114124 KB Output is correct
4 Correct 2487 ms 126364 KB Output is correct
5 Correct 1242 ms 102244 KB Output is correct
6 Correct 119 ms 65216 KB Output is correct
7 Correct 227 ms 72124 KB Output is correct
8 Correct 325 ms 84684 KB Output is correct
9 Correct 253 ms 82236 KB Output is correct
10 Correct 141 ms 64704 KB Output is correct
11 Correct 182 ms 76412 KB Output is correct
12 Correct 243 ms 82920 KB Output is correct
13 Correct 221 ms 82648 KB Output is correct
14 Correct 200 ms 84540 KB Output is correct
15 Correct 185 ms 80952 KB Output is correct
16 Correct 109 ms 63680 KB Output is correct
17 Correct 143 ms 70436 KB Output is correct
18 Correct 203 ms 85108 KB Output is correct
19 Correct 1498 ms 107436 KB Output is correct
20 Correct 2865 ms 133208 KB Output is correct
21 Correct 749 ms 96656 KB Output is correct
22 Correct 748 ms 93740 KB Output is correct
23 Correct 185 ms 65344 KB Output is correct
24 Correct 930 ms 92704 KB Output is correct
25 Execution timed out 3017 ms 132640 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 56656 KB Output is correct
2 Correct 1595 ms 57208 KB Output is correct
3 Correct 374 ms 56916 KB Output is correct
4 Correct 500 ms 56916 KB Output is correct
5 Correct 1742 ms 57660 KB Output is correct
6 Correct 57 ms 56700 KB Output is correct
7 Correct 49 ms 56748 KB Output is correct
8 Correct 50 ms 56660 KB Output is correct
9 Correct 50 ms 56660 KB Output is correct
10 Correct 56 ms 56656 KB Output is correct
11 Correct 802 ms 57168 KB Output is correct
12 Correct 1036 ms 57172 KB Output is correct
13 Correct 1761 ms 57352 KB Output is correct
14 Correct 2191 ms 57984 KB Output is correct
15 Correct 55 ms 56996 KB Output is correct
16 Correct 53 ms 56656 KB Output is correct
17 Correct 51 ms 56652 KB Output is correct
18 Execution timed out 3098 ms 86820 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 56656 KB Output is correct
2 Correct 1595 ms 57208 KB Output is correct
3 Correct 374 ms 56916 KB Output is correct
4 Correct 500 ms 56916 KB Output is correct
5 Correct 1742 ms 57660 KB Output is correct
6 Correct 57 ms 56700 KB Output is correct
7 Correct 49 ms 56748 KB Output is correct
8 Correct 50 ms 56660 KB Output is correct
9 Correct 50 ms 56660 KB Output is correct
10 Correct 56 ms 56656 KB Output is correct
11 Correct 802 ms 57168 KB Output is correct
12 Correct 1036 ms 57172 KB Output is correct
13 Correct 1761 ms 57352 KB Output is correct
14 Correct 2191 ms 57984 KB Output is correct
15 Correct 55 ms 56996 KB Output is correct
16 Correct 53 ms 56656 KB Output is correct
17 Correct 51 ms 56652 KB Output is correct
18 Execution timed out 3098 ms 86820 KB Time limit exceeded
19 Halted 0 ms 0 KB -