oj.uz

Submission #949018

# Submission time Handle Problem Language Result Execution time Memory
949018 2024-03-18T19:27:22 Z Saul0906 Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 116588 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 782 ms 58844 KB Output is correct
2 Correct 1504 ms 58972 KB Output is correct
3 Correct 830 ms 58740 KB Output is correct
4 Correct 917 ms 58964 KB Output is correct
5 Correct 1702 ms 59228 KB Output is correct
6 Correct 49 ms 58448 KB Output is correct
7 Correct 49 ms 58544 KB Output is correct
8 Correct 48 ms 58324 KB Output is correct
9 Correct 50 ms 58448 KB Output is correct
10 Correct 52 ms 58448 KB Output is correct
11 Correct 1130 ms 58792 KB Output is correct
12 Correct 1332 ms 59076 KB Output is correct
13 Correct 1809 ms 58976 KB Output is correct
14 Correct 2198 ms 59108 KB Output is correct
15 Correct 48 ms 58452 KB Output is correct
16 Correct 53 ms 58712 KB Output is correct
17 Correct 59 ms 58452 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 58712 KB Output is correct
2 Correct 59 ms 58452 KB Output is correct
3 Execution timed out 3051 ms 82772 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 58452 KB Output is correct
2 Correct 1089 ms 111420 KB Output is correct
3 Correct 843 ms 111708 KB Output is correct
4 Correct 1331 ms 116588 KB Output is correct
5 Correct 665 ms 98484 KB Output is correct
6 Correct 122 ms 67360 KB Output is correct
7 Incorrect 222 ms 73696 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 58844 KB Output is correct
2 Correct 1504 ms 58972 KB Output is correct
3 Correct 830 ms 58740 KB Output is correct
4 Correct 917 ms 58964 KB Output is correct
5 Correct 1702 ms 59228 KB Output is correct
6 Correct 49 ms 58448 KB Output is correct
7 Correct 49 ms 58544 KB Output is correct
8 Correct 48 ms 58324 KB Output is correct
9 Correct 50 ms 58448 KB Output is correct
10 Correct 52 ms 58448 KB Output is correct
11 Correct 1130 ms 58792 KB Output is correct
12 Correct 1332 ms 59076 KB Output is correct
13 Correct 1809 ms 58976 KB Output is correct
14 Correct 2198 ms 59108 KB Output is correct
15 Correct 48 ms 58452 KB Output is correct
16 Correct 53 ms 58712 KB Output is correct
17 Correct 59 ms 58452 KB Output is correct
18 Execution timed out 3049 ms 82356 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 58844 KB Output is correct
2 Correct 1504 ms 58972 KB Output is correct
3 Correct 830 ms 58740 KB Output is correct
4 Correct 917 ms 58964 KB Output is correct
5 Correct 1702 ms 59228 KB Output is correct
6 Correct 49 ms 58448 KB Output is correct
7 Correct 49 ms 58544 KB Output is correct
8 Correct 48 ms 58324 KB Output is correct
9 Correct 50 ms 58448 KB Output is correct
10 Correct 52 ms 58448 KB Output is correct
11 Correct 1130 ms 58792 KB Output is correct
12 Correct 1332 ms 59076 KB Output is correct
13 Correct 1809 ms 58976 KB Output is correct
14 Correct 2198 ms 59108 KB Output is correct
15 Correct 48 ms 58452 KB Output is correct
16 Correct 53 ms 58712 KB Output is correct
17 Correct 59 ms 58452 KB Output is correct
18 Execution timed out 3049 ms 82356 KB Time limit exceeded
19 Halted 0 ms 0 KB -