oj.uz

Submission #108420

# Submission time Handle Problem Language Result Execution time Memory
108420 2019-04-29T09:17:37 Z mohammad_kilani Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 3000 ms 52300 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010 * 8;
vector< pair<int,int> > arr , arr2;
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;

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) {
	r1 = 1 , r2 = R , c1 = 1 , c2 = C;
	arr2.push_back(make_pair(sr,sc));
	int nr , nc , idx;
	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());
	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++){
		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) {
	r1 = ar , c1 = ac , r2 = br , c2 = bc;
    int ans = 0;
    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 Incorrect 40 ms 38016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 38008 KB Output is correct
2 Correct 38 ms 37888 KB Output is correct
3 Execution timed out 3019 ms 43112 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 37888 KB Output is correct
2 Correct 216 ms 51892 KB Output is correct
3 Correct 203 ms 51772 KB Output is correct
4 Correct 199 ms 52300 KB Output is correct
5 Correct 166 ms 48464 KB Output is correct
6 Correct 66 ms 39404 KB Output is correct
7 Correct 85 ms 40040 KB Output is correct
8 Correct 137 ms 43876 KB Output is correct
9 Correct 124 ms 43740 KB Output is correct
10 Incorrect 62 ms 39408 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 38016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 38016 KB Output isn't correct
2 Halted 0 ms 0 KB -