oj.uz

Submission #949034

# Submission time Handle Problem Language Result Execution time Memory
949034 2024-03-18T20:25:54 Z vjudge1 Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 115208 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)){
		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--;
		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 210 ms 56916 KB Output is correct
2 Correct 817 ms 57032 KB Output is correct
3 Correct 230 ms 56856 KB Output is correct
4 Correct 298 ms 56868 KB Output is correct
5 Correct 924 ms 57100 KB Output is correct
6 Correct 53 ms 56660 KB Output is correct
7 Correct 55 ms 56660 KB Output is correct
8 Correct 53 ms 56640 KB Output is correct
9 Correct 47 ms 56784 KB Output is correct
10 Correct 47 ms 56788 KB Output is correct
11 Correct 505 ms 56904 KB Output is correct
12 Correct 653 ms 56976 KB Output is correct
13 Correct 1130 ms 57236 KB Output is correct
14 Correct 1309 ms 57248 KB Output is correct
15 Correct 50 ms 56776 KB Output is correct
16 Correct 56 ms 56780 KB Output is correct
17 Correct 51 ms 56780 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 56780 KB Output is correct
2 Correct 51 ms 56780 KB Output is correct
3 Execution timed out 3038 ms 70272 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 56776 KB Output is correct
2 Correct 2080 ms 107456 KB Output is correct
3 Correct 588 ms 85560 KB Output is correct
4 Correct 2015 ms 115208 KB Output is correct
5 Correct 709 ms 84900 KB Output is correct
6 Correct 94 ms 65220 KB Output is correct
7 Incorrect 177 ms 68788 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 56916 KB Output is correct
2 Correct 817 ms 57032 KB Output is correct
3 Correct 230 ms 56856 KB Output is correct
4 Correct 298 ms 56868 KB Output is correct
5 Correct 924 ms 57100 KB Output is correct
6 Correct 53 ms 56660 KB Output is correct
7 Correct 55 ms 56660 KB Output is correct
8 Correct 53 ms 56640 KB Output is correct
9 Correct 47 ms 56784 KB Output is correct
10 Correct 47 ms 56788 KB Output is correct
11 Correct 505 ms 56904 KB Output is correct
12 Correct 653 ms 56976 KB Output is correct
13 Correct 1130 ms 57236 KB Output is correct
14 Correct 1309 ms 57248 KB Output is correct
15 Correct 50 ms 56776 KB Output is correct
16 Correct 56 ms 56780 KB Output is correct
17 Correct 51 ms 56780 KB Output is correct
18 Execution timed out 3051 ms 72960 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 56916 KB Output is correct
2 Correct 817 ms 57032 KB Output is correct
3 Correct 230 ms 56856 KB Output is correct
4 Correct 298 ms 56868 KB Output is correct
5 Correct 924 ms 57100 KB Output is correct
6 Correct 53 ms 56660 KB Output is correct
7 Correct 55 ms 56660 KB Output is correct
8 Correct 53 ms 56640 KB Output is correct
9 Correct 47 ms 56784 KB Output is correct
10 Correct 47 ms 56788 KB Output is correct
11 Correct 505 ms 56904 KB Output is correct
12 Correct 653 ms 56976 KB Output is correct
13 Correct 1130 ms 57236 KB Output is correct
14 Correct 1309 ms 57248 KB Output is correct
15 Correct 50 ms 56776 KB Output is correct
16 Correct 56 ms 56780 KB Output is correct
17 Correct 51 ms 56780 KB Output is correct
18 Execution timed out 3051 ms 72960 KB Time limit exceeded
19 Halted 0 ms 0 KB -