oj.uz

Submission #949022

# Submission time Handle Problem Language Result Execution time Memory
949022 2024-03-18T19:44:32 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 107280 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});
	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 156 ms 56916 KB Output is correct
2 Correct 634 ms 57020 KB Output is correct
3 Correct 183 ms 56660 KB Output is correct
4 Correct 244 ms 56884 KB Output is correct
5 Correct 726 ms 57108 KB Output is correct
6 Correct 50 ms 56784 KB Output is correct
7 Correct 49 ms 56616 KB Output is correct
8 Correct 50 ms 56660 KB Output is correct
9 Correct 52 ms 56784 KB Output is correct
10 Correct 55 ms 56656 KB Output is correct
11 Correct 430 ms 56656 KB Output is correct
12 Correct 548 ms 57164 KB Output is correct
13 Correct 893 ms 57372 KB Output is correct
14 Correct 964 ms 57248 KB Output is correct
15 Correct 51 ms 56652 KB Output is correct
16 Correct 60 ms 56660 KB Output is correct
17 Correct 50 ms 56764 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 56660 KB Output is correct
2 Correct 50 ms 56764 KB Output is correct
3 Execution timed out 3032 ms 73340 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 56652 KB Output is correct
2 Correct 1267 ms 95856 KB Output is correct
3 Correct 1099 ms 96460 KB Output is correct
4 Correct 1794 ms 107280 KB Output is correct
5 Correct 806 ms 86984 KB Output is correct
6 Correct 109 ms 63940 KB Output is correct
7 Incorrect 167 ms 68792 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 56916 KB Output is correct
2 Correct 634 ms 57020 KB Output is correct
3 Correct 183 ms 56660 KB Output is correct
4 Correct 244 ms 56884 KB Output is correct
5 Correct 726 ms 57108 KB Output is correct
6 Correct 50 ms 56784 KB Output is correct
7 Correct 49 ms 56616 KB Output is correct
8 Correct 50 ms 56660 KB Output is correct
9 Correct 52 ms 56784 KB Output is correct
10 Correct 55 ms 56656 KB Output is correct
11 Correct 430 ms 56656 KB Output is correct
12 Correct 548 ms 57164 KB Output is correct
13 Correct 893 ms 57372 KB Output is correct
14 Correct 964 ms 57248 KB Output is correct
15 Correct 51 ms 56652 KB Output is correct
16 Correct 60 ms 56660 KB Output is correct
17 Correct 50 ms 56764 KB Output is correct
18 Execution timed out 3018 ms 73588 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 56916 KB Output is correct
2 Correct 634 ms 57020 KB Output is correct
3 Correct 183 ms 56660 KB Output is correct
4 Correct 244 ms 56884 KB Output is correct
5 Correct 726 ms 57108 KB Output is correct
6 Correct 50 ms 56784 KB Output is correct
7 Correct 49 ms 56616 KB Output is correct
8 Correct 50 ms 56660 KB Output is correct
9 Correct 52 ms 56784 KB Output is correct
10 Correct 55 ms 56656 KB Output is correct
11 Correct 430 ms 56656 KB Output is correct
12 Correct 548 ms 57164 KB Output is correct
13 Correct 893 ms 57372 KB Output is correct
14 Correct 964 ms 57248 KB Output is correct
15 Correct 51 ms 56652 KB Output is correct
16 Correct 60 ms 56660 KB Output is correct
17 Correct 50 ms 56764 KB Output is correct
18 Execution timed out 3018 ms 73588 KB Time limit exceeded
19 Halted 0 ms 0 KB -