oj.uz

Submission #949032

# Submission time Handle Problem Language Result Execution time Memory
949032 2024-03-18T20:23:25 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 107760 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++;
		else if(e.fi>ar && !river.count({e.fi-1,e.se})) e.fi--;
		else if(e.se<bc && !river.count({e.fi,e.se+1})) e.se++;
		else 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 203 ms 56844 KB Output is correct
2 Correct 1018 ms 57304 KB Output is correct
3 Correct 222 ms 56656 KB Output is correct
4 Correct 322 ms 56816 KB Output is correct
5 Correct 1226 ms 57116 KB Output is correct
6 Correct 48 ms 56660 KB Output is correct
7 Correct 49 ms 56656 KB Output is correct
8 Correct 49 ms 56656 KB Output is correct
9 Correct 49 ms 56656 KB Output is correct
10 Correct 48 ms 56656 KB Output is correct
11 Correct 577 ms 56912 KB Output is correct
12 Correct 822 ms 56988 KB Output is correct
13 Correct 1293 ms 57128 KB Output is correct
14 Correct 1925 ms 57244 KB Output is correct
15 Correct 48 ms 56656 KB Output is correct
16 Correct 49 ms 56676 KB Output is correct
17 Correct 49 ms 56764 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56676 KB Output is correct
2 Correct 49 ms 56764 KB Output is correct
3 Execution timed out 3063 ms 72364 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 56656 KB Output is correct
2 Correct 1316 ms 95940 KB Output is correct
3 Correct 1184 ms 95788 KB Output is correct
4 Correct 1844 ms 107760 KB Output is correct
5 Correct 816 ms 86252 KB Output is correct
6 Correct 130 ms 63896 KB Output is correct
7 Incorrect 190 ms 68536 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 56844 KB Output is correct
2 Correct 1018 ms 57304 KB Output is correct
3 Correct 222 ms 56656 KB Output is correct
4 Correct 322 ms 56816 KB Output is correct
5 Correct 1226 ms 57116 KB Output is correct
6 Correct 48 ms 56660 KB Output is correct
7 Correct 49 ms 56656 KB Output is correct
8 Correct 49 ms 56656 KB Output is correct
9 Correct 49 ms 56656 KB Output is correct
10 Correct 48 ms 56656 KB Output is correct
11 Correct 577 ms 56912 KB Output is correct
12 Correct 822 ms 56988 KB Output is correct
13 Correct 1293 ms 57128 KB Output is correct
14 Correct 1925 ms 57244 KB Output is correct
15 Correct 48 ms 56656 KB Output is correct
16 Correct 49 ms 56676 KB Output is correct
17 Correct 49 ms 56764 KB Output is correct
18 Execution timed out 3041 ms 73908 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 56844 KB Output is correct
2 Correct 1018 ms 57304 KB Output is correct
3 Correct 222 ms 56656 KB Output is correct
4 Correct 322 ms 56816 KB Output is correct
5 Correct 1226 ms 57116 KB Output is correct
6 Correct 48 ms 56660 KB Output is correct
7 Correct 49 ms 56656 KB Output is correct
8 Correct 49 ms 56656 KB Output is correct
9 Correct 49 ms 56656 KB Output is correct
10 Correct 48 ms 56656 KB Output is correct
11 Correct 577 ms 56912 KB Output is correct
12 Correct 822 ms 56988 KB Output is correct
13 Correct 1293 ms 57128 KB Output is correct
14 Correct 1925 ms 57244 KB Output is correct
15 Correct 48 ms 56656 KB Output is correct
16 Correct 49 ms 56676 KB Output is correct
17 Correct 49 ms 56764 KB Output is correct
18 Execution timed out 3041 ms 73908 KB Time limit exceeded
19 Halted 0 ms 0 KB -