oj.uz

Submission #108422

# Submission time Handle Problem Language Result Execution time Memory
108422 2019-04-29T09:30:59 Z mohammad_kilani Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 142792 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();
	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 = arr2;
	r1 = 1 , r2 = n , c1 = 1 , c2 = m;
    for(int i = ar;i<=br;i++){
    	if(in(i , ac - 1))
    		arr3.push_back(make_pair(i,ac - 1));
    	if(in(i , bc + 1))
    		arr3.push_back(make_pair(i,bc + 1));
    }
    for(int i = ac;i<=bc;i++){
    	if(in(ar - 1, i))
    		arr3.push_back(make_pair(ar - 1,i));
    	if(in(br + 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++;
    }
    long long sz = (r2 - r1 + 1) * (c2 - c1 + 1);
    for(int i = 0 ;i < (int)arr2.size();i++){
    	if(in(arr2[i].first,arr2[i].second))
    		sz--;
    }
    if(ans == 0)
    	ans = 1;
    if(sz == 0)
    	ans = 0;
    return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 37980 KB Output is correct
2 Correct 925 ms 38172 KB Output is correct
3 Correct 309 ms 38120 KB Output is correct
4 Correct 358 ms 38016 KB Output is correct
5 Correct 963 ms 38204 KB Output is correct
6 Correct 36 ms 37876 KB Output is correct
7 Correct 34 ms 37880 KB Output is correct
8 Correct 35 ms 37888 KB Output is correct
9 Correct 41 ms 37880 KB Output is correct
10 Correct 38 ms 37880 KB Output is correct
11 Incorrect 404 ms 38092 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 37880 KB Output is correct
2 Correct 38 ms 37880 KB Output is correct
3 Execution timed out 3042 ms 58488 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 37980 KB Output is correct
2 Correct 806 ms 94516 KB Output is correct
3 Correct 707 ms 94212 KB Output is correct
4 Correct 384 ms 66876 KB Output is correct
5 Correct 380 ms 65640 KB Output is correct
6 Correct 931 ms 116048 KB Output is correct
7 Incorrect 1258 ms 142792 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 37980 KB Output is correct
2 Correct 925 ms 38172 KB Output is correct
3 Correct 309 ms 38120 KB Output is correct
4 Correct 358 ms 38016 KB Output is correct
5 Correct 963 ms 38204 KB Output is correct
6 Correct 36 ms 37876 KB Output is correct
7 Correct 34 ms 37880 KB Output is correct
8 Correct 35 ms 37888 KB Output is correct
9 Correct 41 ms 37880 KB Output is correct
10 Correct 38 ms 37880 KB Output is correct
11 Incorrect 404 ms 38092 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 37980 KB Output is correct
2 Correct 925 ms 38172 KB Output is correct
3 Correct 309 ms 38120 KB Output is correct
4 Correct 358 ms 38016 KB Output is correct
5 Correct 963 ms 38204 KB Output is correct
6 Correct 36 ms 37876 KB Output is correct
7 Correct 34 ms 37880 KB Output is correct
8 Correct 35 ms 37888 KB Output is correct
9 Correct 41 ms 37880 KB Output is correct
10 Correct 38 ms 37880 KB Output is correct
11 Incorrect 404 ms 38092 KB Output isn't correct
12 Halted 0 ms 0 KB -