Submission #264881

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
264881	2020-08-14T10:49:06 Z	_7_7_	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	3000 ms	118788 KB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>                                           
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;  
typedef unsigned long long ull;         
typedef vector < pii > vpii;                                   	
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;
 
typedef tree < int, null_type, less < int >, rb_tree_tag, tree_order_statistics_node_update > ordered_set;
 
const int inf = 1e9, maxn = 2e5 + 48, mod = 998244353, N = 2e5 + 12;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 300;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = acos(-1);
const ll INF = 1e18;


int ar, ac, br, bc, ans;
set < pii > q, qq, was;

	
void init(int R, int C, int sr, int sc, int M, char *S) {
	q.insert(mp(sr, sc));

	for (int i = 0; i < M; ++i) {
		if (S[i] == 'N')
			--sr;
		else if (S[i] == 'S')	
			++sr;
		else if (S[i] == 'W')	
			--sc;
		else 
			++sc;	 			
		q.insert(mp(sr, sc));		
	}
}

bool in (int x, int y) {
	return ar <= x && x <= br && ac <= y && y <= bc;
}


void dfs (pii x) {
	was.insert(x);
	for (int i = 0; i < 4; ++i) {
		int tox = x.f + dx[i], toy = x.s + dy[i];
		if (in(tox, toy) && !was.count(mp(tox, toy)) && qq.count(mp(tox, toy)))
			dfs(mp(tox, toy));
	}
}

void Add (int x, int y) {
	for (int i = -1; i <= 1; ++i)
		for (int j = -1; j <= 1; ++j) {
			int tox = x + i, toy = y + j;
			if (in(tox, toy) && !q.count(mp(tox, toy)))
				qq.insert(mp(tox, toy));
		}
}

int colour(int Ar, int Ac, int Br, int Bc) {
	ar = Ar, ac = Ac, br = Br, bc = Bc;

	qq.clear();
	was.clear();
	for (auto x : q)
		Add(x.f, x.s);


	bool ok = 0;
	for (auto x : qq)
		if (x.f == Ar || x.f == Br || x.s == Ac || x.s == Bc) {
			ok = 1; 
			break;
		}

//	if (ok) {
		for (int i = Ar; i <= Br; ++i){
		    if (!q.count(mp(i, Ac)))
				qq.insert(mp(i, Ac));
			if (!q.count(mp(i, Bc)))
				qq.insert(mp(i, Bc));
		}

		for (int j = Ac; j <= Bc; ++j) {
			if (!q.count(mp(Ar, j)))
				qq.insert(mp(Ar, j));
			if (!q.count(mp(Br, j)))
				qq.insert(mp(Br, j));
		}			
//	}

 
	ans = 0;
	for (auto x : qq)
		if (!was.count(x)) {
			dfs(x);
			++ans;
		}
 

    return ans;
}

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:98:7: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   98 |  bool ok = 0;
      |       ^~

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	384 KB	Output is correct
2	Correct	218 ms	524 KB	Output is correct
3	Correct	97 ms	384 KB	Output is correct
4	Correct	118 ms	384 KB	Output is correct
5	Correct	256 ms	564 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	188 ms	504 KB	Output is correct
12	Correct	272 ms	504 KB	Output is correct
13	Correct	549 ms	624 KB	Output is correct
14	Correct	518 ms	632 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	0 ms	256 KB	Output is correct
17	Correct	0 ms	256 KB	Output is correct

Subtask #2

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Execution timed out	3084 ms	50552 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	699 ms	58360 KB	Output is correct
3	Correct	672 ms	58360 KB	Output is correct
4	Correct	708 ms	58360 KB	Output is correct
5	Correct	325 ms	28280 KB	Output is correct
6	Correct	718 ms	86724 KB	Output is correct
7	Incorrect	1135 ms	118788 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #4

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	384 KB	Output is correct
2	Correct	218 ms	524 KB	Output is correct
3	Correct	97 ms	384 KB	Output is correct
4	Correct	118 ms	384 KB	Output is correct
5	Correct	256 ms	564 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	188 ms	504 KB	Output is correct
12	Correct	272 ms	504 KB	Output is correct
13	Correct	549 ms	624 KB	Output is correct
14	Correct	518 ms	632 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	0 ms	256 KB	Output is correct
17	Correct	0 ms	256 KB	Output is correct
18	Execution timed out	3066 ms	9020 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	384 KB	Output is correct
2	Correct	218 ms	524 KB	Output is correct
3	Correct	97 ms	384 KB	Output is correct
4	Correct	118 ms	384 KB	Output is correct
5	Correct	256 ms	564 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	1 ms	256 KB	Output is correct
8	Correct	1 ms	256 KB	Output is correct
9	Correct	0 ms	256 KB	Output is correct
10	Correct	1 ms	256 KB	Output is correct
11	Correct	188 ms	504 KB	Output is correct
12	Correct	272 ms	504 KB	Output is correct
13	Correct	549 ms	624 KB	Output is correct
14	Correct	518 ms	632 KB	Output is correct
15	Correct	1 ms	256 KB	Output is correct
16	Correct	0 ms	256 KB	Output is correct
17	Correct	0 ms	256 KB	Output is correct
18	Execution timed out	3066 ms	9020 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-