oj.uz

Submission #949017

# Submission time Handle Problem Language Result Execution time Memory
949017 2024-03-18T19:26:14 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 116448 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;
int dsu[1000005]{};

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});
	repa(e,nriver) 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,1e6+5) if(dsu[i]==i) c++;
	rep(i,1,timer+5) dsu[i]=0;
	return c;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 58588 KB Output is correct
2 Correct 1492 ms 59036 KB Output is correct
3 Correct 835 ms 58720 KB Output is correct
4 Correct 925 ms 58964 KB Output is correct
5 Correct 1698 ms 59160 KB Output is correct
6 Correct 51 ms 58460 KB Output is correct
7 Correct 55 ms 58468 KB Output is correct
8 Correct 52 ms 58488 KB Output is correct
9 Correct 50 ms 58452 KB Output is correct
10 Correct 53 ms 58520 KB Output is correct
11 Correct 1132 ms 58804 KB Output is correct
12 Correct 1372 ms 58972 KB Output is correct
13 Correct 1822 ms 59232 KB Output is correct
14 Correct 2190 ms 59256 KB Output is correct
15 Correct 48 ms 58320 KB Output is correct
16 Correct 53 ms 58452 KB Output is correct
17 Correct 56 ms 58516 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 58452 KB Output is correct
2 Correct 56 ms 58516 KB Output is correct
3 Execution timed out 3015 ms 82732 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 58320 KB Output is correct
2 Correct 1130 ms 112524 KB Output is correct
3 Correct 854 ms 111756 KB Output is correct
4 Correct 1350 ms 116448 KB Output is correct
5 Correct 675 ms 98236 KB Output is correct
6 Correct 138 ms 67308 KB Output is correct
7 Incorrect 229 ms 73616 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 58588 KB Output is correct
2 Correct 1492 ms 59036 KB Output is correct
3 Correct 835 ms 58720 KB Output is correct
4 Correct 925 ms 58964 KB Output is correct
5 Correct 1698 ms 59160 KB Output is correct
6 Correct 51 ms 58460 KB Output is correct
7 Correct 55 ms 58468 KB Output is correct
8 Correct 52 ms 58488 KB Output is correct
9 Correct 50 ms 58452 KB Output is correct
10 Correct 53 ms 58520 KB Output is correct
11 Correct 1132 ms 58804 KB Output is correct
12 Correct 1372 ms 58972 KB Output is correct
13 Correct 1822 ms 59232 KB Output is correct
14 Correct 2190 ms 59256 KB Output is correct
15 Correct 48 ms 58320 KB Output is correct
16 Correct 53 ms 58452 KB Output is correct
17 Correct 56 ms 58516 KB Output is correct
18 Execution timed out 3034 ms 82712 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 58588 KB Output is correct
2 Correct 1492 ms 59036 KB Output is correct
3 Correct 835 ms 58720 KB Output is correct
4 Correct 925 ms 58964 KB Output is correct
5 Correct 1698 ms 59160 KB Output is correct
6 Correct 51 ms 58460 KB Output is correct
7 Correct 55 ms 58468 KB Output is correct
8 Correct 52 ms 58488 KB Output is correct
9 Correct 50 ms 58452 KB Output is correct
10 Correct 53 ms 58520 KB Output is correct
11 Correct 1132 ms 58804 KB Output is correct
12 Correct 1372 ms 58972 KB Output is correct
13 Correct 1822 ms 59232 KB Output is correct
14 Correct 2190 ms 59256 KB Output is correct
15 Correct 48 ms 58320 KB Output is correct
16 Correct 53 ms 58452 KB Output is correct
17 Correct 56 ms 58516 KB Output is correct
18 Execution timed out 3034 ms 82712 KB Time limit exceeded
19 Halted 0 ms 0 KB -