oj.uz

Submission #949029

# Submission time Handle Problem Language Result Execution time Memory
949029 2024-03-18T20:13:25 Z Saul0906 Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 3000 ms 194412 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;

int timer=1;
map<pii,int> pos;
set<int> river;
set<int> rows[200005], cols[200005];
vector<pii> nriver;

void init(int R, int C, int sr, int sc, int M, char *S){
	if(!pos[{sr,sc}]) pos[{sr,sc}]=timer++;
	river.insert(pos[{sr,sc}]);
	rep(i,0,2e5+5){
		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++;
		if(!pos[{sr,sc}]) pos[{sr,sc}]=timer++;
		river.insert(pos[{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<int> vis;
vector<int> dsu(10000005);

int find(int a){
	if(!dsu[a] || dsu[a]==a) return a;
	return dsu[a]=find(dsu[a]);
}

void join(int a, int 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;
	if(!pos[{x,y}]) pos[{x,y}]=timer++;
	vis.insert(pos[{x,y}]);
	join(pos[{x,y}],pos[{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(pos[{x,y1}]) && !vis.count(pos[{x,y1}])) dfs(x,y1,ar,ac,br,bc);
	if(!river.count(pos[{x,y2}]) && !vis.count(pos[{x,y2}])) dfs(x,y2,ar,ac,br,bc);
	if(!river.count(pos[{x1,y}]) && !vis.count(pos[{x1,y}])) dfs(x1,y,ar,ac,br,bc);
	if(!river.count(pos[{x2,y}]) && !vis.count(pos[{x2,y}])) dfs(x2,y,ar,ac,br,bc);
	if(!river.count(pos[{x,y1}])) join(pos[{x,y}],pos[{x,y1}]);
	if(!river.count(pos[{x,y2}])) join(pos[{x,y}],pos[{x,y2}]);
	if(!river.count(pos[{x1,y}])) join(pos[{x,y}],pos[{x1,y}]);
	if(!river.count(pos[{x2,y}])) join(pos[{x,y}],pos[{x2,y}]);
}

int colour(int ar, int ac, int br, int bc){
	vis.clear();
	int c=0;
	if(!pos[{ar,ac}]) pos[{ar,ac}]=timer++;
	if(!pos[{br,bc}]) pos[{br,bc}]=timer++;
	nriver.pb({ar,ac});
	nriver.pb({br,bc});
	vector<pii> ext;
	repa(e,nriver) if(!river.count(pos[e]) && !vis.count(pos[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});
		dfs(e.fi,e.se,ar,ac,br,bc);
	}
	repa(e,nriver) if(!river.count(pos[e]) && !vis.count(pos[e])) dfs(e.fi,e.se,ar,ac,br,bc);
	repa(e,ext) if(!river.count(pos[e]) && !vis.count(pos[e])) dfs(e.fi,e.se,ar,ac,br,bc);
	nriver.pop_back();
	nriver.pop_back();
	rep(i,1,1e7+5) if(dsu[i]==i) c++;
	rep(i,1,timer+5) dsu[i]=0;
	return c;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3022 ms 96080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 95828 KB Output is correct
2 Correct 145 ms 95824 KB Output is correct
3 Execution timed out 3047 ms 134368 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 95828 KB Output is correct
2 Correct 1861 ms 173800 KB Output is correct
3 Correct 1488 ms 173036 KB Output is correct
4 Correct 1881 ms 167976 KB Output is correct
5 Correct 1179 ms 154296 KB Output is correct
6 Correct 182 ms 106944 KB Output is correct
7 Correct 307 ms 111296 KB Output is correct
8 Correct 570 ms 145004 KB Output is correct
9 Correct 496 ms 140236 KB Output is correct
10 Correct 187 ms 105200 KB Output is correct
11 Correct 396 ms 127344 KB Output is correct
12 Correct 592 ms 150832 KB Output is correct
13 Correct 476 ms 153048 KB Output is correct
14 Correct 408 ms 140084 KB Output is correct
15 Correct 424 ms 139836 KB Output is correct
16 Correct 173 ms 104884 KB Output is correct
17 Correct 252 ms 112796 KB Output is correct
18 Correct 427 ms 132248 KB Output is correct
19 Correct 1330 ms 166148 KB Output is correct
20 Correct 2119 ms 184080 KB Output is correct
21 Correct 819 ms 145156 KB Output is correct
22 Correct 796 ms 138680 KB Output is correct
23 Correct 222 ms 105156 KB Output is correct
24 Correct 801 ms 131980 KB Output is correct
25 Execution timed out 3091 ms 194412 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3022 ms 96080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3022 ms 96080 KB Time limit exceeded
2 Halted 0 ms 0 KB -