제출 #108427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108427		mohammad_kilani	무지개나라 (APIO17_rainbow)	C++17	11 / 100	3112 ms	293028 KiB

rainbow

#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 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26