글 읽기 - 형님들 반례좀 부탁드리겠습니다!

devbelly 3년 전 0

게시판 반례는 다 통과하는데 전혀 모르겠습니다. ㅜ

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int n, u, v;
int ppl[10000];
bool visited[10000];
vector<vector<int>> adj;
vector<vector<int>> dir;
int cache[10000][2][2];
int maxSum(int here, bool makewusu,bool near) {
	int& ret = cache[here][makewusu][near];
	if (ret != -1) return ret;
	ret = 0;
	if (makewusu) { // case 1 : here이 우수마을로 선정!
		ret += ppl[here];
		for (auto there : dir[here]) {
			ret += maxSum(there, !makewusu, true);
		}
	}
	else if (!makewusu && near) { // case 2 : here은 우수마을이 아니지만 주변에 우수가 있다
		for (auto there : dir[here]) {
			ret += max(maxSum(there, !makewusu, false),maxSum(there,makewusu,false));
		}
	}
	else if (!makewusu && !near) {//case 3 :here은 우수마을이 아니고 주변에 우수가 없다.
		for (auto there : dir[here]) {
			ret += maxSum(there, !makewusu, false);
		}
	}
	return ret;
}

void dfs(int node) {
	visited[node] = true;
	for (auto there : adj[node]) {
		if (!visited[there]) {
			dir[node].emplace_back(there);
			dfs(there);
		}
	}
}

int main() {
	memset(cache, -1, sizeof(cache));
	FAST;
	cin >> n;
	adj.resize(n);
	dir.resize(n);
	rep(i, n) cin >> ppl[i];
	rep(i, n - 1) {
		cin >> u >> v;
		u--;
		v--;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	dfs(0);
	cout << max(maxSum(0, 1, 0), maxSum(0, 0, 0));
	
	
	
		


	return 0;
}

wjdclgns12 3년 전 6

반례입니다.

6
10 1 1 1 10 10
1 2
2 3
3 4
4 5
3 6
// Answer : 30
// Output : 21

devbelly 3년 전 0

형님 너무 감사합니다

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

문제

문제

출처

ICPC

형님들 반례좀 부탁드리겠습니다!

devbelly 3년 전 0

wjdclgns12 3년 전 6

devbelly 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말