oj.uz

Submission #949026

# Submission time Handle Problem Language Result Execution time Memory
949026 2024-03-18T20:01:47 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 134492 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)){
		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});
	}
	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 299 ms 56856 KB Output is correct
2 Correct 1600 ms 57540 KB Output is correct
3 Correct 371 ms 56892 KB Output is correct
4 Correct 506 ms 56916 KB Output is correct
5 Correct 1773 ms 57768 KB Output is correct
6 Correct 50 ms 56584 KB Output is correct
7 Correct 50 ms 56784 KB Output is correct
8 Correct 57 ms 56764 KB Output is correct
9 Correct 51 ms 56656 KB Output is correct
10 Correct 49 ms 56656 KB Output is correct
11 Correct 829 ms 57228 KB Output is correct
12 Correct 1060 ms 57056 KB Output is correct
13 Correct 1796 ms 57668 KB Output is correct
14 Correct 2260 ms 57976 KB Output is correct
15 Correct 49 ms 56660 KB Output is correct
16 Correct 50 ms 56656 KB Output is correct
17 Correct 49 ms 56608 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 56656 KB Output is correct
2 Correct 49 ms 56608 KB Output is correct
3 Execution timed out 3049 ms 77644 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 56660 KB Output is correct
2 Correct 2128 ms 117796 KB Output is correct
3 Correct 1846 ms 114472 KB Output is correct
4 Correct 2484 ms 125156 KB Output is correct
5 Correct 1248 ms 101760 KB Output is correct
6 Correct 121 ms 65200 KB Output is correct
7 Correct 228 ms 71056 KB Output is correct
8 Correct 351 ms 85292 KB Output is correct
9 Correct 255 ms 80604 KB Output is correct
10 Correct 142 ms 64704 KB Output is correct
11 Correct 193 ms 77128 KB Output is correct
12 Correct 234 ms 83256 KB Output is correct
13 Correct 222 ms 85284 KB Output is correct
14 Correct 195 ms 83256 KB Output is correct
15 Correct 192 ms 81908 KB Output is correct
16 Correct 117 ms 64528 KB Output is correct
17 Correct 143 ms 70508 KB Output is correct
18 Correct 209 ms 83304 KB Output is correct
19 Correct 1489 ms 106960 KB Output is correct
20 Correct 2866 ms 134020 KB Output is correct
21 Correct 780 ms 96300 KB Output is correct
22 Correct 778 ms 93956 KB Output is correct
23 Correct 185 ms 65500 KB Output is correct
24 Correct 955 ms 93672 KB Output is correct
25 Execution timed out 3061 ms 134492 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 56856 KB Output is correct
2 Correct 1600 ms 57540 KB Output is correct
3 Correct 371 ms 56892 KB Output is correct
4 Correct 506 ms 56916 KB Output is correct
5 Correct 1773 ms 57768 KB Output is correct
6 Correct 50 ms 56584 KB Output is correct
7 Correct 50 ms 56784 KB Output is correct
8 Correct 57 ms 56764 KB Output is correct
9 Correct 51 ms 56656 KB Output is correct
10 Correct 49 ms 56656 KB Output is correct
11 Correct 829 ms 57228 KB Output is correct
12 Correct 1060 ms 57056 KB Output is correct
13 Correct 1796 ms 57668 KB Output is correct
14 Correct 2260 ms 57976 KB Output is correct
15 Correct 49 ms 56660 KB Output is correct
16 Correct 50 ms 56656 KB Output is correct
17 Correct 49 ms 56608 KB Output is correct
18 Execution timed out 3051 ms 86396 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 56856 KB Output is correct
2 Correct 1600 ms 57540 KB Output is correct
3 Correct 371 ms 56892 KB Output is correct
4 Correct 506 ms 56916 KB Output is correct
5 Correct 1773 ms 57768 KB Output is correct
6 Correct 50 ms 56584 KB Output is correct
7 Correct 50 ms 56784 KB Output is correct
8 Correct 57 ms 56764 KB Output is correct
9 Correct 51 ms 56656 KB Output is correct
10 Correct 49 ms 56656 KB Output is correct
11 Correct 829 ms 57228 KB Output is correct
12 Correct 1060 ms 57056 KB Output is correct
13 Correct 1796 ms 57668 KB Output is correct
14 Correct 2260 ms 57976 KB Output is correct
15 Correct 49 ms 56660 KB Output is correct
16 Correct 50 ms 56656 KB Output is correct
17 Correct 49 ms 56608 KB Output is correct
18 Execution timed out 3051 ms 86396 KB Time limit exceeded
19 Halted 0 ms 0 KB -