oj.uz

Submission #108427

# Submission time Handle Problem Language Result Execution time Memory
108427 2019-04-29T09:39:34 Z mohammad_kilani Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 293028 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 8000010;
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 337 ms 188280 KB Output is correct
2 Correct 1031 ms 188408 KB Output is correct
3 Correct 421 ms 188412 KB Output is correct
4 Correct 513 ms 188368 KB Output is correct
5 Correct 1106 ms 188408 KB Output is correct
6 Correct 178 ms 188152 KB Output is correct
7 Correct 186 ms 188232 KB Output is correct
8 Correct 173 ms 188280 KB Output is correct
9 Correct 168 ms 188280 KB Output is correct
10 Correct 161 ms 188276 KB Output is correct
11 Correct 517 ms 188312 KB Output is correct
12 Correct 751 ms 188408 KB Output is correct
13 Correct 1360 ms 188592 KB Output is correct
14 Correct 1456 ms 188408 KB Output is correct
15 Correct 176 ms 188248 KB Output is correct
16 Correct 192 ms 188320 KB Output is correct
17 Correct 177 ms 188208 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 188320 KB Output is correct
2 Correct 177 ms 188208 KB Output is correct
3 Execution timed out 3112 ms 220040 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 188248 KB Output is correct
2 Correct 867 ms 244780 KB Output is correct
3 Correct 900 ms 244472 KB Output is correct
4 Correct 639 ms 225400 KB Output is correct
5 Correct 486 ms 215892 KB Output is correct
6 Correct 1046 ms 266468 KB Output is correct
7 Incorrect 1278 ms 293028 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 188280 KB Output is correct
2 Correct 1031 ms 188408 KB Output is correct
3 Correct 421 ms 188412 KB Output is correct
4 Correct 513 ms 188368 KB Output is correct
5 Correct 1106 ms 188408 KB Output is correct
6 Correct 178 ms 188152 KB Output is correct
7 Correct 186 ms 188232 KB Output is correct
8 Correct 173 ms 188280 KB Output is correct
9 Correct 168 ms 188280 KB Output is correct
10 Correct 161 ms 188276 KB Output is correct
11 Correct 517 ms 188312 KB Output is correct
12 Correct 751 ms 188408 KB Output is correct
13 Correct 1360 ms 188592 KB Output is correct
14 Correct 1456 ms 188408 KB Output is correct
15 Correct 176 ms 188248 KB Output is correct
16 Correct 192 ms 188320 KB Output is correct
17 Correct 177 ms 188208 KB Output is correct
18 Execution timed out 3045 ms 195588 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 188280 KB Output is correct
2 Correct 1031 ms 188408 KB Output is correct
3 Correct 421 ms 188412 KB Output is correct
4 Correct 513 ms 188368 KB Output is correct
5 Correct 1106 ms 188408 KB Output is correct
6 Correct 178 ms 188152 KB Output is correct
7 Correct 186 ms 188232 KB Output is correct
8 Correct 173 ms 188280 KB Output is correct
9 Correct 168 ms 188280 KB Output is correct
10 Correct 161 ms 188276 KB Output is correct
11 Correct 517 ms 188312 KB Output is correct
12 Correct 751 ms 188408 KB Output is correct
13 Correct 1360 ms 188592 KB Output is correct
14 Correct 1456 ms 188408 KB Output is correct
15 Correct 176 ms 188248 KB Output is correct
16 Correct 192 ms 188320 KB Output is correct
17 Correct 177 ms 188208 KB Output is correct
18 Execution timed out 3045 ms 195588 KB Time limit exceeded
19 Halted 0 ms 0 KB -