oj.uz

Submission #949019

# Submission time Handle Problem Language Result Execution time Memory
949019 2024-03-18T19:28:21 Z Saul0906 Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 106888 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.insert({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++;
		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});
	repa(e,nriver) 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++;
	return c;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 56920 KB Output is correct
2 Correct 626 ms 57296 KB Output is correct
3 Correct 186 ms 56660 KB Output is correct
4 Correct 270 ms 56912 KB Output is correct
5 Correct 714 ms 56916 KB Output is correct
6 Correct 50 ms 56624 KB Output is correct
7 Correct 47 ms 56580 KB Output is correct
8 Correct 48 ms 56660 KB Output is correct
9 Correct 49 ms 56660 KB Output is correct
10 Correct 47 ms 56660 KB Output is correct
11 Correct 430 ms 56900 KB Output is correct
12 Correct 536 ms 57168 KB Output is correct
13 Correct 888 ms 56912 KB Output is correct
14 Correct 976 ms 57244 KB Output is correct
15 Correct 47 ms 56660 KB Output is correct
16 Correct 47 ms 56692 KB Output is correct
17 Correct 67 ms 56888 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 56692 KB Output is correct
2 Correct 67 ms 56888 KB Output is correct
3 Execution timed out 3043 ms 73324 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 56660 KB Output is correct
2 Correct 1254 ms 96792 KB Output is correct
3 Correct 1136 ms 96020 KB Output is correct
4 Correct 1834 ms 106888 KB Output is correct
5 Correct 808 ms 87372 KB Output is correct
6 Correct 88 ms 64196 KB Output is correct
7 Incorrect 164 ms 69844 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 56920 KB Output is correct
2 Correct 626 ms 57296 KB Output is correct
3 Correct 186 ms 56660 KB Output is correct
4 Correct 270 ms 56912 KB Output is correct
5 Correct 714 ms 56916 KB Output is correct
6 Correct 50 ms 56624 KB Output is correct
7 Correct 47 ms 56580 KB Output is correct
8 Correct 48 ms 56660 KB Output is correct
9 Correct 49 ms 56660 KB Output is correct
10 Correct 47 ms 56660 KB Output is correct
11 Correct 430 ms 56900 KB Output is correct
12 Correct 536 ms 57168 KB Output is correct
13 Correct 888 ms 56912 KB Output is correct
14 Correct 976 ms 57244 KB Output is correct
15 Correct 47 ms 56660 KB Output is correct
16 Correct 47 ms 56692 KB Output is correct
17 Correct 67 ms 56888 KB Output is correct
18 Execution timed out 3045 ms 73528 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 56920 KB Output is correct
2 Correct 626 ms 57296 KB Output is correct
3 Correct 186 ms 56660 KB Output is correct
4 Correct 270 ms 56912 KB Output is correct
5 Correct 714 ms 56916 KB Output is correct
6 Correct 50 ms 56624 KB Output is correct
7 Correct 47 ms 56580 KB Output is correct
8 Correct 48 ms 56660 KB Output is correct
9 Correct 49 ms 56660 KB Output is correct
10 Correct 47 ms 56660 KB Output is correct
11 Correct 430 ms 56900 KB Output is correct
12 Correct 536 ms 57168 KB Output is correct
13 Correct 888 ms 56912 KB Output is correct
14 Correct 976 ms 57244 KB Output is correct
15 Correct 47 ms 56660 KB Output is correct
16 Correct 47 ms 56692 KB Output is correct
17 Correct 67 ms 56888 KB Output is correct
18 Execution timed out 3045 ms 73528 KB Time limit exceeded
19 Halted 0 ms 0 KB -