oj.uz

답안 #200302

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200302 2020-02-06T09:21:11 Z dimash241 무지개나라 (APIO17_rainbow) C++17
11 / 100
 25 ms 760 KB 
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>
#include "rainbow.h"

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

inline void Input_Output () {
	//freopen(".in", "r", stdin);
   //freopen(".out", "w", stdout);
}

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k, q;
int u[55][55];
int d[55][55];
int timer;

inline void moveto (int &x, int &y, char c) {
	if (c == 'N') x--;
	if (c == 'S') x++;
	if (c == 'W') y--;
	if (c == 'E') y++;
	assert(x > 0 && y > 0 && x <= n && y <= m);
} 
int lx, ly, rx, ry; 

bool cordi (int x, int y) {
	if(!(x >= lx && y >= ly && x <= rx && y <= ry)) return 0;
	return !d[x][y];
}

void init(int _n, int _m, int x, int y, int _k, char *s) {
	n = _n, m = _m, k = _k;
	d[x][y] = 1;
	for (int i = 0; i < k; ++i) {
		moveto(x, y, s[i]);
	//	cout << x << ' ' << y << '\n';
		d[x][y] = 1;
	}
}

void dfs (int ax, int bx) {
	u[ax][bx] = timer;
//	cout << ax << ' ' << bx << '\n';
	for (int dir = 0; dir < 4; ++dir) {
		int ay = ax + dx[dir];
		int by = bx + dy[dir];
		
		if (cordi(ay, by) && u[ay][by] != timer)
			dfs(ay, by);
	}
}

int colour(int ar, int ac, int br, int bc) {
	lx = ar;
	rx = br;
	ly = ac;
	ry = bc;
	++timer;
	int cnt = 0;
	for (int ax = ar; ax <= br; ++ax) {
		for (int bx = ac; bx <= bc; ++bx) {
			if (cordi(ax, bx) && u[ax][bx] != timer) {
				//cout << ax << ' ' << bx << '\n';
				dfs(ax, bx);
				++cnt;
			}
		}
	}
    return cnt;
}
/*
static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}

// B...a*/

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 25 ms 376 KB Output is correct
4 Correct 25 ms 376 KB Output is correct
5 Correct 12 ms 376 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 22 ms 376 KB Output is correct
12 Correct 19 ms 376 KB Output is correct
13 Correct 15 ms 376 KB Output is correct
14 Correct 12 ms 376 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 4 ms 256 KB Output is correct
17 Correct 5 ms 256 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Runtime error 8 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB Output is correct
2 Runtime error 5 ms 636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 25 ms 376 KB Output is correct
4 Correct 25 ms 376 KB Output is correct
5 Correct 12 ms 376 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 22 ms 376 KB Output is correct
12 Correct 19 ms 376 KB Output is correct
13 Correct 15 ms 376 KB Output is correct
14 Correct 12 ms 376 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 4 ms 256 KB Output is correct
17 Correct 5 ms 256 KB Output is correct
18 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 25 ms 376 KB Output is correct
4 Correct 25 ms 376 KB Output is correct
5 Correct 12 ms 376 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 22 ms 376 KB Output is correct
12 Correct 19 ms 376 KB Output is correct
13 Correct 15 ms 376 KB Output is correct
14 Correct 12 ms 376 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 4 ms 256 KB Output is correct
17 Correct 5 ms 256 KB Output is correct
18 Runtime error 6 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -