oj.uz

Submission #949046

# Submission time Handle Problem Language Result Execution time Memory
949046 2024-03-18T20:58:11 Z Saul0906 Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 137608 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(!vis.count({x,y1})) dfs(x,y1,ar,ac,br,bc);}
	if(!river.count({x,y2})) {join({x,y},{x,y2}); if(!vis.count({x,y2})) dfs(x,y2,ar,ac,br,bc);}
	if(!river.count({x1,y})) {join({x,y},{x1,y}); if(!vis.count({x1,y})) dfs(x1,y,ar,ac,br,bc);}
	if(!river.count({x2,y})) {join({x,y},{x2,y}); if(!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 284 ms 56668 KB Output is correct
2 Correct 1530 ms 57248 KB Output is correct
3 Correct 353 ms 56660 KB Output is correct
4 Correct 481 ms 56912 KB Output is correct
5 Correct 1699 ms 57544 KB Output is correct
6 Correct 51 ms 56716 KB Output is correct
7 Correct 48 ms 56668 KB Output is correct
8 Correct 48 ms 56660 KB Output is correct
9 Correct 49 ms 56764 KB Output is correct
10 Correct 66 ms 56816 KB Output is correct
11 Correct 800 ms 57084 KB Output is correct
12 Correct 992 ms 57252 KB Output is correct
13 Correct 1723 ms 57480 KB Output is correct
14 Correct 2161 ms 57720 KB Output is correct
15 Correct 48 ms 56712 KB Output is correct
16 Correct 53 ms 56660 KB Output is correct
17 Correct 49 ms 56780 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 56660 KB Output is correct
2 Correct 49 ms 56780 KB Output is correct
3 Execution timed out 3022 ms 80448 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 56712 KB Output is correct
2 Correct 1985 ms 116800 KB Output is correct
3 Correct 1590 ms 113052 KB Output is correct
4 Correct 2212 ms 127708 KB Output is correct
5 Correct 1119 ms 101288 KB Output is correct
6 Correct 113 ms 65976 KB Output is correct
7 Correct 219 ms 70896 KB Output is correct
8 Correct 320 ms 83552 KB Output is correct
9 Correct 240 ms 80948 KB Output is correct
10 Correct 158 ms 64656 KB Output is correct
11 Correct 184 ms 78192 KB Output is correct
12 Correct 211 ms 83508 KB Output is correct
13 Correct 238 ms 84268 KB Output is correct
14 Correct 196 ms 84188 KB Output is correct
15 Correct 194 ms 78532 KB Output is correct
16 Correct 114 ms 64968 KB Output is correct
17 Correct 141 ms 70580 KB Output is correct
18 Correct 202 ms 83256 KB Output is correct
19 Correct 1478 ms 106840 KB Output is correct
20 Correct 2651 ms 133432 KB Output is correct
21 Correct 692 ms 97584 KB Output is correct
22 Correct 690 ms 94304 KB Output is correct
23 Correct 174 ms 65456 KB Output is correct
24 Correct 833 ms 93484 KB Output is correct
25 Execution timed out 3065 ms 137608 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 56668 KB Output is correct
2 Correct 1530 ms 57248 KB Output is correct
3 Correct 353 ms 56660 KB Output is correct
4 Correct 481 ms 56912 KB Output is correct
5 Correct 1699 ms 57544 KB Output is correct
6 Correct 51 ms 56716 KB Output is correct
7 Correct 48 ms 56668 KB Output is correct
8 Correct 48 ms 56660 KB Output is correct
9 Correct 49 ms 56764 KB Output is correct
10 Correct 66 ms 56816 KB Output is correct
11 Correct 800 ms 57084 KB Output is correct
12 Correct 992 ms 57252 KB Output is correct
13 Correct 1723 ms 57480 KB Output is correct
14 Correct 2161 ms 57720 KB Output is correct
15 Correct 48 ms 56712 KB Output is correct
16 Correct 53 ms 56660 KB Output is correct
17 Correct 49 ms 56780 KB Output is correct
18 Execution timed out 3054 ms 86676 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 56668 KB Output is correct
2 Correct 1530 ms 57248 KB Output is correct
3 Correct 353 ms 56660 KB Output is correct
4 Correct 481 ms 56912 KB Output is correct
5 Correct 1699 ms 57544 KB Output is correct
6 Correct 51 ms 56716 KB Output is correct
7 Correct 48 ms 56668 KB Output is correct
8 Correct 48 ms 56660 KB Output is correct
9 Correct 49 ms 56764 KB Output is correct
10 Correct 66 ms 56816 KB Output is correct
11 Correct 800 ms 57084 KB Output is correct
12 Correct 992 ms 57252 KB Output is correct
13 Correct 1723 ms 57480 KB Output is correct
14 Correct 2161 ms 57720 KB Output is correct
15 Correct 48 ms 56712 KB Output is correct
16 Correct 53 ms 56660 KB Output is correct
17 Correct 49 ms 56780 KB Output is correct
18 Execution timed out 3054 ms 86676 KB Time limit exceeded
19 Halted 0 ms 0 KB -