oj.uz

Submission #108426

# Submission time Handle Problem Language Result Execution time Memory
108426 2019-04-29T09:38:15 Z mohammad_kilani Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 142920 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010 * 8;
vector< pair<int,int> > arr , arr2, arr3;
vector < int > g[N];
int vis[N] , vi = 0;
int dr[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};
int dc[8] = {1 , 0 , -1 , 0 , 1 , -1, 1, -1};


int r1 , c1 , r2 , c2 , n , m;

inline bool in(int r,int c){
	return (r >= r1 && r <= r2 && c >= c1 && c <= c2);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	n = R , m = C;
	arr2.push_back(make_pair(sr,sc));
	for(int i = 0;i < M;i++){
		if(S[i] == 'N') sr--; else if(S[i] == 'S') sr++; else if(S[i] == 'E') sc++; else sc--;
			arr2.push_back(make_pair(sr,sc));
	}
	sort(arr2.begin(),arr2.end());
	arr2.resize(unique(arr2.begin(),arr2.end()) - arr2.begin());
}

void make_arr(vector< pair<int,int> > &arr2){
	arr.clear();
	r1 = 1 , r2 = n , c1 = 1 , c2 = m;
	int sr , sc , nr , nc, idx;
	for(int i = 0 ;i < (int)arr2.size();i++){
		sr = arr2[i].first;
		sc = arr2[i].second;
		for(int j = 0 ;j < 8 ;j++){
			nr = sr + dr[j];
			nc = sc + dc[j];
			if(in(nr,nc) && !binary_search(arr2.begin(),arr2.end() , make_pair(nr,nc))){
				arr.push_back(make_pair(nr,nc));
			}
		}
	}
	sort(arr.begin(),arr.end());
	arr.resize(unique(arr.begin(),arr.end()) - arr.begin());
	for(int i = 0 ; i < (int)arr.size();i++){
		g[i].clear();
		sr = arr[i].first;
		sc = arr[i].second;
		for(int j = 0 ;j < 4;j++){
			nr = sr + dr[j];
			nc = sc + dc[j];
			idx = lower_bound(arr.begin(),arr.end(),make_pair(nr , nc)) - arr.begin();
			if(idx != (int)arr.size() && arr[idx].first == nr && arr[idx].second == nc){
				g[i].push_back(idx);
			}
		}
	}

}

void DFS(int node){
	vis[node] = vi;
	for(int i = 0 ;i < (int)g[node].size();i++){
		if(vis[g[node][i]] == vi || !in(arr[g[node][i]].first,arr[g[node][i]].second)) continue;
		DFS(g[node][i]);
	}
}

int colour(int ar, int ac, int br, int bc) {
    int ans = 0;
    arr3.clear();
    arr3 = arr2;
    for(int i = ar;i<=br;i++){
    	arr3.push_back(make_pair(i,ac - 1));
    	arr3.push_back(make_pair(i,bc + 1));
    }
    for(int i = ac;i<=bc;i++){
    	arr3.push_back(make_pair(ar - 1,i));
    	arr3.push_back(make_pair(br + 1,i));
    }
    sort(arr3.begin(),arr3.end());
    arr3.resize(unique(arr3.begin(),arr3.end()) - arr3.begin());
	make_arr(arr3);
	r1 = ar , c1 = ac , r2 = br , c2 = bc;
    vi++;
    for(int i = 0 ;i < (int)arr.size();i++){
    	if(vis[i] == vi || !in(arr[i].first,arr[i].second)) continue;
    	DFS(i);
    	ans++;
    }
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 37888 KB Output is correct
2 Correct 885 ms 38108 KB Output is correct
3 Correct 300 ms 37880 KB Output is correct
4 Correct 348 ms 38136 KB Output is correct
5 Correct 951 ms 38236 KB Output is correct
6 Correct 35 ms 37888 KB Output is correct
7 Correct 35 ms 37860 KB Output is correct
8 Correct 36 ms 38012 KB Output is correct
9 Correct 36 ms 37852 KB Output is correct
10 Correct 34 ms 37880 KB Output is correct
11 Correct 382 ms 38136 KB Output is correct
12 Correct 576 ms 38136 KB Output is correct
13 Correct 1169 ms 38392 KB Output is correct
14 Correct 1266 ms 38136 KB Output is correct
15 Correct 38 ms 37980 KB Output is correct
16 Correct 39 ms 37880 KB Output is correct
17 Correct 36 ms 37888 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37880 KB Output is correct
2 Correct 36 ms 37888 KB Output is correct
3 Execution timed out 3042 ms 69868 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 37980 KB Output is correct
2 Correct 713 ms 94348 KB Output is correct
3 Correct 675 ms 94104 KB Output is correct
4 Correct 462 ms 75156 KB Output is correct
5 Correct 411 ms 65528 KB Output is correct
6 Correct 909 ms 116068 KB Output is correct
7 Incorrect 1106 ms 142920 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 37888 KB Output is correct
2 Correct 885 ms 38108 KB Output is correct
3 Correct 300 ms 37880 KB Output is correct
4 Correct 348 ms 38136 KB Output is correct
5 Correct 951 ms 38236 KB Output is correct
6 Correct 35 ms 37888 KB Output is correct
7 Correct 35 ms 37860 KB Output is correct
8 Correct 36 ms 38012 KB Output is correct
9 Correct 36 ms 37852 KB Output is correct
10 Correct 34 ms 37880 KB Output is correct
11 Correct 382 ms 38136 KB Output is correct
12 Correct 576 ms 38136 KB Output is correct
13 Correct 1169 ms 38392 KB Output is correct
14 Correct 1266 ms 38136 KB Output is correct
15 Correct 38 ms 37980 KB Output is correct
16 Correct 39 ms 37880 KB Output is correct
17 Correct 36 ms 37888 KB Output is correct
18 Execution timed out 3040 ms 45300 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 37888 KB Output is correct
2 Correct 885 ms 38108 KB Output is correct
3 Correct 300 ms 37880 KB Output is correct
4 Correct 348 ms 38136 KB Output is correct
5 Correct 951 ms 38236 KB Output is correct
6 Correct 35 ms 37888 KB Output is correct
7 Correct 35 ms 37860 KB Output is correct
8 Correct 36 ms 38012 KB Output is correct
9 Correct 36 ms 37852 KB Output is correct
10 Correct 34 ms 37880 KB Output is correct
11 Correct 382 ms 38136 KB Output is correct
12 Correct 576 ms 38136 KB Output is correct
13 Correct 1169 ms 38392 KB Output is correct
14 Correct 1266 ms 38136 KB Output is correct
15 Correct 38 ms 37980 KB Output is correct
16 Correct 39 ms 37880 KB Output is correct
17 Correct 36 ms 37888 KB Output is correct
18 Execution timed out 3040 ms 45300 KB Time limit exceeded
19 Halted 0 ms 0 KB -