글 읽기 - 23044 어떤 반례가 있는지 모르겠습니다.

dkvltmxhf 2년 전 0

부수면 안되는 노드에서 K만큼 거리를 구한 후, 부술 수 있는 모든 노드를 부수는 parametric search를 이용했습니다.

O(N)시간에 탐색을 위하여 새로 부술 수 있는 경우 pair<int,int>.second 값을 0으로 초기화해주며 bfs를 돌렸읍니다.

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define all(x) x.begin(), x.end()
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define MS(x,y) memset(x,y,sizeof(x))
#define rep(x) for(int i=0;i<x;i++)
#define repp(x) for(int j=0;j<x;j++)
#define READGRID(x,y) rep(x)repp(y) cin>>arr[i][j]
#define INF 2147483647
#define MAX 200002
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const int dx[] = { -1, 1, 0, 0, -1, 1, 1, -1 };
const int dy[] = { 0, 0, -1, 1, 1, 1, -1, -1 };
vector<int> adj[MAX];
int ans = INF, n, a, b, boom[MAX], des[MAX], visited[MAX];
queue<pi> q;



bool condition(int k) {

	for (int i = 1; i <= n; i++) {
		if (!boom[i] && !visited[i]) {
			visited[i] = true;

			q.push({ i,0 });
			while (!q.empty()) {
				pi now = q.front(); q.pop();
				if (now.Y == k - 1) continue;
				for (auto next : adj[now.X]) {
					if (visited[next]) continue;
					visited[next] = true;
					if (!boom[next]) {
						q.push({ next,0 });
					}
					else
						q.push({ next,now.Y + 1 });
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (boom[i] && !visited[i] && !des[i]) {
			des[i] = true;
			q.push({ i,0 });
			while (!q.empty()) {
				pi now = q.front(); q.pop();
				if (now.Y == k - 1) continue;
				for (auto next : adj[now.X]) {
					if (des[next]) continue;
					des[next] = true;
					if (boom[next] && !visited[next]) {
						q.push({ next,0 });
					}
					else 
						q.push({ next,now.Y + 1 });
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		if (boom[i] && !des[i])
			return false;
	}
	return true;
}

int main(void) {
	fastio
	cin >> n;
	rep(n)cin >> boom[i + 1];
	rep(n - 1) {
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	int s = 1, e = n;
	while (s <= e) {
		MS(des, 0);
		MS(visited, 0);
		int mid = s + e >> 1;

		if (condition(mid)) {
			s = mid + 1;
		}
		else {
			e = mid - 1;
		}
	}

	cout << e;
	return 0;
}

ho94949 2년 전 1

답 7이에요

19
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

23044 어떤 반례가 있는지 모르겠습니다.

dkvltmxhf 2년 전 0

ho94949 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말