Submission #949028

#	Time	Username	Problem	Language	Result	Execution time	Memory
949028		vjudge1	Land of the Rainbow Gold (APIO17_rainbow)	C++17	0 / 100	3069 ms	190836 KiB

rainbow

#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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26