oj.uz

Submission #949030

# Submission time Handle Problem Language Result Execution time Memory
949030 2024-03-18T20:20:40 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 107032 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.clear();
	nriver.clear();
	river.insert({sr,sc});
	rep(i,0,2e5+5){
		cols[i].clear();
		rows[i].clear();
		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});
	vector<pii> ext;
	repa(e,nriver) if(!river.count(e) && !vis.count(e)){
		if(e.fi<br && !river.count({e.fi+1,e.se})) e.fi++;
		if(e.fi>ar && !river.count({e.fi-1,e.se})) e.fi--;
		if(e.se<bc && !river.count({e.fi,e.se+1})) e.se++;
		if(e.se>ac && !river.count({e.fi,e.se-1})) e.se--;
	}
	repa(e,nriver) if(!river.count(e) && !vis.count(e)) dfs(e.fi,e.se,ar,ac,br,bc);
	repa(e,ext) 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++;
	//, cout<<e.fi.fi<<" "<<e.fi.se<<endl;
	return c;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 56656 KB Output is correct
2 Correct 1100 ms 57300 KB Output is correct
3 Correct 231 ms 56860 KB Output is correct
4 Correct 322 ms 56880 KB Output is correct
5 Correct 1295 ms 57116 KB Output is correct
6 Correct 56 ms 56976 KB Output is correct
7 Correct 50 ms 56668 KB Output is correct
8 Correct 48 ms 56700 KB Output is correct
9 Correct 48 ms 56656 KB Output is correct
10 Correct 48 ms 56656 KB Output is correct
11 Correct 588 ms 56900 KB Output is correct
12 Correct 826 ms 56980 KB Output is correct
13 Correct 1370 ms 57376 KB Output is correct
14 Correct 1897 ms 57384 KB Output is correct
15 Correct 56 ms 56608 KB Output is correct
16 Correct 49 ms 56660 KB Output is correct
17 Correct 55 ms 56720 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56660 KB Output is correct
2 Correct 55 ms 56720 KB Output is correct
3 Execution timed out 3040 ms 72612 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 56608 KB Output is correct
2 Correct 1327 ms 95916 KB Output is correct
3 Correct 1174 ms 95900 KB Output is correct
4 Correct 1865 ms 107032 KB Output is correct
5 Correct 835 ms 87016 KB Output is correct
6 Correct 115 ms 64704 KB Output is correct
7 Incorrect 190 ms 68804 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 56656 KB Output is correct
2 Correct 1100 ms 57300 KB Output is correct
3 Correct 231 ms 56860 KB Output is correct
4 Correct 322 ms 56880 KB Output is correct
5 Correct 1295 ms 57116 KB Output is correct
6 Correct 56 ms 56976 KB Output is correct
7 Correct 50 ms 56668 KB Output is correct
8 Correct 48 ms 56700 KB Output is correct
9 Correct 48 ms 56656 KB Output is correct
10 Correct 48 ms 56656 KB Output is correct
11 Correct 588 ms 56900 KB Output is correct
12 Correct 826 ms 56980 KB Output is correct
13 Correct 1370 ms 57376 KB Output is correct
14 Correct 1897 ms 57384 KB Output is correct
15 Correct 56 ms 56608 KB Output is correct
16 Correct 49 ms 56660 KB Output is correct
17 Correct 55 ms 56720 KB Output is correct
18 Execution timed out 3034 ms 73300 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 56656 KB Output is correct
2 Correct 1100 ms 57300 KB Output is correct
3 Correct 231 ms 56860 KB Output is correct
4 Correct 322 ms 56880 KB Output is correct
5 Correct 1295 ms 57116 KB Output is correct
6 Correct 56 ms 56976 KB Output is correct
7 Correct 50 ms 56668 KB Output is correct
8 Correct 48 ms 56700 KB Output is correct
9 Correct 48 ms 56656 KB Output is correct
10 Correct 48 ms 56656 KB Output is correct
11 Correct 588 ms 56900 KB Output is correct
12 Correct 826 ms 56980 KB Output is correct
13 Correct 1370 ms 57376 KB Output is correct
14 Correct 1897 ms 57384 KB Output is correct
15 Correct 56 ms 56608 KB Output is correct
16 Correct 49 ms 56660 KB Output is correct
17 Correct 55 ms 56720 KB Output is correct
18 Execution timed out 3034 ms 73300 KB Time limit exceeded
19 Halted 0 ms 0 KB -