oj.uz

Submission #949028

# Submission time Handle Problem Language Result Execution time Memory
949028 2024-03-18T20:12:28 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 190836 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 3034 ms 95812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 95752 KB Output is correct
2 Correct 157 ms 96076 KB Output is correct
3 Execution timed out 3055 ms 134096 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 95824 KB Output is correct
2 Correct 1944 ms 173124 KB Output is correct
3 Correct 1508 ms 171616 KB Output is correct
4 Correct 1893 ms 166592 KB Output is correct
5 Correct 1162 ms 154292 KB Output is correct
6 Correct 184 ms 106168 KB Output is correct
7 Correct 311 ms 111324 KB Output is correct
8 Correct 564 ms 144652 KB Output is correct
9 Correct 495 ms 140472 KB Output is correct
10 Correct 188 ms 105316 KB Output is correct
11 Correct 385 ms 127156 KB Output is correct
12 Correct 590 ms 153064 KB Output is correct
13 Correct 479 ms 151576 KB Output is correct
14 Correct 418 ms 138636 KB Output is correct
15 Correct 426 ms 139772 KB Output is correct
16 Correct 171 ms 104888 KB Output is correct
17 Correct 247 ms 113356 KB Output is correct
18 Correct 440 ms 134776 KB Output is correct
19 Correct 1344 ms 168428 KB Output is correct
20 Correct 2221 ms 182232 KB Output is correct
21 Correct 834 ms 144136 KB Output is correct
22 Correct 792 ms 138368 KB Output is correct
23 Correct 222 ms 105296 KB Output is correct
24 Correct 813 ms 129968 KB Output is correct
25 Execution timed out 3069 ms 190836 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 3034 ms 95812 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 3034 ms 95812 KB Time limit exceeded
2 Halted 0 ms 0 KB -