oj.uz

Submission #108425

# Submission time Handle Problem Language Result Execution time Memory
108425 2019-04-29T09:33:59 Z mohammad_kilani Land of the Rainbow Gold (APIO17_rainbow) C++17
11 / 100
 3000 ms 142944 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++){
    	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++;
    }
    long long sz = (long long)(r2 - r1 + 1) * (long long)(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
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 37880 KB Output is correct
2 Correct 888 ms 38172 KB Output is correct
3 Correct 314 ms 38008 KB Output is correct
4 Correct 364 ms 38008 KB Output is correct
5 Correct 1008 ms 38268 KB Output is correct
6 Correct 36 ms 37880 KB Output is correct
7 Correct 35 ms 37880 KB Output is correct
8 Correct 38 ms 37880 KB Output is correct
9 Correct 34 ms 37888 KB Output is correct
10 Correct 42 ms 37880 KB Output is correct
11 Correct 374 ms 38008 KB Output is correct
12 Correct 616 ms 38020 KB Output is correct
13 Correct 1195 ms 38264 KB Output is correct
14 Correct 1275 ms 38268 KB Output is correct
15 Correct 36 ms 37880 KB Output is correct
16 Correct 39 ms 37908 KB Output is correct
17 Correct 35 ms 37820 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 37908 KB Output is correct
2 Correct 35 ms 37820 KB Output is correct
3 Execution timed out 3025 ms 70020 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37880 KB Output is correct
2 Correct 787 ms 94484 KB Output is correct
3 Correct 725 ms 94232 KB Output is correct
4 Correct 511 ms 75176 KB Output is correct
5 Correct 410 ms 65640 KB Output is correct
6 Correct 883 ms 116088 KB Output is correct
7 Incorrect 1309 ms 142944 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 37880 KB Output is correct
2 Correct 888 ms 38172 KB Output is correct
3 Correct 314 ms 38008 KB Output is correct
4 Correct 364 ms 38008 KB Output is correct
5 Correct 1008 ms 38268 KB Output is correct
6 Correct 36 ms 37880 KB Output is correct
7 Correct 35 ms 37880 KB Output is correct
8 Correct 38 ms 37880 KB Output is correct
9 Correct 34 ms 37888 KB Output is correct
10 Correct 42 ms 37880 KB Output is correct
11 Correct 374 ms 38008 KB Output is correct
12 Correct 616 ms 38020 KB Output is correct
13 Correct 1195 ms 38264 KB Output is correct
14 Correct 1275 ms 38268 KB Output is correct
15 Correct 36 ms 37880 KB Output is correct
16 Correct 39 ms 37908 KB Output is correct
17 Correct 35 ms 37820 KB Output is correct
18 Execution timed out 3021 ms 45376 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 37880 KB Output is correct
2 Correct 888 ms 38172 KB Output is correct
3 Correct 314 ms 38008 KB Output is correct
4 Correct 364 ms 38008 KB Output is correct
5 Correct 1008 ms 38268 KB Output is correct
6 Correct 36 ms 37880 KB Output is correct
7 Correct 35 ms 37880 KB Output is correct
8 Correct 38 ms 37880 KB Output is correct
9 Correct 34 ms 37888 KB Output is correct
10 Correct 42 ms 37880 KB Output is correct
11 Correct 374 ms 38008 KB Output is correct
12 Correct 616 ms 38020 KB Output is correct
13 Correct 1195 ms 38264 KB Output is correct
14 Correct 1275 ms 38268 KB Output is correct
15 Correct 36 ms 37880 KB Output is correct
16 Correct 39 ms 37908 KB Output is correct
17 Correct 35 ms 37820 KB Output is correct
18 Execution timed out 3021 ms 45376 KB Time limit exceeded
19 Halted 0 ms 0 KB -