oj.uz

Submission #403640

# Submission time Handle Problem Language Result Execution time Memory
403640 2021-05-13T10:37:23 Z yoavL Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 1048580 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <fstream>
#include <iomanip>


using namespace std;

using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vld = vector<ld>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using pb = pair<bool, bool>;
using vpb = vector<pb>;
using vvpb = vector<vpb>;
using vi = vector<int>;
using vvi = vector<vi>;

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;


#define FAST        ios_base::sync_with_stdio(0)
#define FASTIN		cin.tie(0)
#define FASTOUT		cout.tie(0)

#define upmin(a, b) a = min(a, b)
#define upmax(a, b) a = max(a, b)

#define whatvec(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define prv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define wpr(x) cout << #x << " = " << (x) << endl;
#define wprv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define wprv2(v) cout << #v << ": " << endl; for(auto it : v) {for(auto it2 : it) cout << it2 << " "; cout << endl;} cout << endl;
#define what(x) cout << #x << " = " << (x) << "\n";
#define pr(x) cout <<x << endl;

#define rep(i,s,e) for(ll i = s;i < e; i++)
#define rep(i, e) for(ll i = 0; i < e; i++)
#define all(x) x.begin(),x.end()
#define pb push_back


vll xdir = { -1, 1, 0, 0 };
vll ydir = { 0, 0, -1, 1 };



string path;
ll r, c, sr, sc, m;

ll minr, maxr, minc, maxc;
vvb taken;


void init(int R, int C, int SR, int SC, int M, char * S)
{
	r = R, c = C, sr = SR-1, sc = SC-1, m = M;
	//wpr(r);
	//wpr(c);
	path.resize(m);
	for (ll i = 0; i < m; i++) {
		path[i] = S[i];
	}
	//wpr(path);
	taken.resize(r, vb(c, 0));
	taken[sr][sc] = 1;
	map<char, ll> mp;
	mp['N'] = 0;
	mp['S'] = 1;
	mp['W'] = 2;
	mp['E'] = 3;
	ll curx = sr, cury = sc;
	for (ll i = 0; i < m; i++) {
		ll ind = mp[path[i]];
		curx += xdir[ind];
		cury += ydir[ind];
		taken[curx][cury] = 1;
	}
	//wprv2(taken);
}


void dfs(vvb &vis, ll curx, ll cury)
{

	vis[curx][cury] = true;
	for (ll i = 0; i < 4; i++) {
		ll x = curx + xdir[i];
		ll y = cury + ydir[i];

		if (x < minr || x > maxr || y < minc || y > maxc) continue;

		if (vis[x][y]) continue;

		if (taken[x][y]) continue;
		dfs(vis, x, y);
	}
}


int colour(int ar, int ac, int br, int bc)
{
	ar--, ac--, br--, bc--;
	minr = ar, maxr = br, minc = ac, maxc = bc;

	vvb vis(r, vb(c, 0));
	ll res = 0;
	for (ll i = minr; i <= maxr; i++) {
		for (ll j = minc; j <= maxc; j++) {
			if (vis[i][j]) continue;
			if (taken[i][j]) continue;
			res++;
			//wpr(i);
			//wpr(j);
			dfs(vis, i, j);
		}
	}
	return res;
}



/*

6 4 9 4 
3 3 
NWESSWEWS 
2 3 2 3 
3 2 4 4 
5 3 6 4 
1 2 5 3 


*/

Compilation message

rainbow.cpp:60: warning: "rep" redefined
   60 | #define rep(i, e) for(ll i = 0; i < e; i++)
      | 
rainbow.cpp:59: note: this is the location of the previous definition
   59 | #define rep(i,s,e) for(ll i = s;i < e; i++)
      |

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 308 KB Output is correct
2 Correct 19 ms 348 KB Output is correct
3 Correct 30 ms 444 KB Output is correct
4 Correct 30 ms 332 KB Output is correct
5 Correct 18 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 26 ms 424 KB Output is correct
12 Correct 24 ms 332 KB Output is correct
13 Correct 21 ms 384 KB Output is correct
14 Correct 21 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 296 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Execution timed out 3067 ms 18156 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 204 KB Output is correct
2 Runtime error 554 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 308 KB Output is correct
2 Correct 19 ms 348 KB Output is correct
3 Correct 30 ms 444 KB Output is correct
4 Correct 30 ms 332 KB Output is correct
5 Correct 18 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 26 ms 424 KB Output is correct
12 Correct 24 ms 332 KB Output is correct
13 Correct 21 ms 384 KB Output is correct
14 Correct 21 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Execution timed out 3065 ms 8144 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 308 KB Output is correct
2 Correct 19 ms 348 KB Output is correct
3 Correct 30 ms 444 KB Output is correct
4 Correct 30 ms 332 KB Output is correct
5 Correct 18 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 26 ms 424 KB Output is correct
12 Correct 24 ms 332 KB Output is correct
13 Correct 21 ms 384 KB Output is correct
14 Correct 21 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Execution timed out 3065 ms 8144 KB Time limit exceeded
19 Halted 0 ms 0 KB -