Anniversary/권영기 - Revision history

Maintenance script: Repair batch-0008 pages from live compare

2026-03-27T01:40:36Z

Repair batch-0008 pages from live compare

← Older revision		Revision as of 01:40, 27 March 2026
Line 22:		Line 22:
	using namespace std;		using namespace std;
	const int N = 6020;		const int N = 6020;
	int n, intimacies[N];		int n, intimacies[N];
	int d[N][2]; // d[i][0] - participate, d[i][1] - not participate		int d[N][2]; // d[i][0] - participate, d[i][1] - not participate
	int boss[N]; // at first, every staff's boss is himself. Thus boss[i] = i;		int boss[N]; // at first, every staff's boss is himself. Thus boss[i] = i;
	vector < list < int > > staffs; // vector[i]		vector < list < int > > staffs; // vector[i]
	vector < pair <int, int> > staff_priority_queue; // vector[i].first = level of Tree, vectors[i].second = idx.		vector < pair <int, int> > staff_priority_queue; // vector[i].first = level of Tree, vectors[i].second = idx.
	int cmp(pair <int, int> s, pair <int, int> w){		int cmp(pair <int, int> s, pair <int, int> w){
	return s.first > w.first;		return s.first > w.first;
	}		}
	void leveling_node(int node, int level){		void leveling_node(int node, int level){
	staff_priority_queue[node].first = level;		staff_priority_queue[node].first = level;
	for(list<int>::iterator it = staffs[node].begin(); it != staffs[node].end(); it++){		for(list<int>::iterator it = staffs[node].begin(); it != staffs[node].end(); it++){
	leveling_node(*it, level + 1);		leveling_node(*it, level + 1);
	}		}
Line 41:		Line 41:
	staff_priority_queue.resize(n + 10);		staff_priority_queue.resize(n + 10);
	staffs.resize(n + 10);		staffs.resize(n + 10);
	staff_priority_queue[0].first = -1;		staff_priority_queue[0].first = -1;
	staff_priority_queue[0].second = -1;		staff_priority_queue[0].second = -1;
	for(int i = 1; i<=n; i++){		for(int i = 1; i<=n; i++){
	cin>>intimacies[i];		cin>>intimacies[i];
	staff_priority_queue[i].second = i;		staff_priority_queue[i].second = i;
	staff_priority_queue[i].first = -1;		staff_priority_queue[i].first = -1;
	boss[i] = i;		boss[i] = i;
	}		}
	int L, k, m = 0;		int L, k, m = 0;
Line 53:		Line 53:
	cin>>L>>k;		cin>>L>>k;
	if(L == 0 && k == 0)break;		if(L == 0 && k == 0)break;
	staffs[k].push_back(L);		staffs[k].push_back(L);
	staff_priority_queue[k].first++;		staff_priority_queue[k].first++;
	boss[L] = k;		boss[L] = k;
	//at the end, the root of subtree only satisfy 'boss[i] == i'.		//at the end, the root of subtree only satisfy 'boss[i] == i'.
	m++;		m++;
	};		};
Line 66:		Line 66:

	for(int i = 1; i<=n; i++){		for(int i = 1; i<=n; i++){
	if(boss[i] == i){		if(boss[i] == i){
	leveling_node(i, 0);		leveling_node(i, 0);
	}		}
Line 76:		Line 76:
	for(int i = 0; i<n; i++){		for(int i = 0; i<n; i++){
	int sum_of_participate = 0, sum_of_not_participate = 0;		int sum_of_participate = 0, sum_of_not_participate = 0;
	int idx = staff_priority_queue[i].second;		int idx = staff_priority_queue[i].second;
	for(list<int>::iterator it = staffs[idx].begin(); it != staffs[idx].end(); it++){		for(list<int>::iterator it = staffs[idx].begin(); it != staffs[idx].end(); it++){
	if(d[it][0] >= 0)sum_of_participate += d[it][0];		if(d[it][0] >= 0)sum_of_participate += d[it][0];
	if(d[it][1] >= 0)sum_of_not_participate += d[it][1];		if(d[it][1] >= 0)sum_of_not_participate += d[it][1];
	}		}
	d[idx][0] = sum_of_not_participate + intimacies[idx];		d[idx][0] = sum_of_not_participate + intimacies[idx];
	d[idx][1] = max(sum_of_participate, sum_of_not_participate);		d[idx][1] = max(sum_of_participate, sum_of_not_participate);
	if(ans < d[idx][0])ans = d[idx][0];		if(ans < d[idx][0])ans = d[idx][0];
	if(ans < d[idx][1])ans = d[idx][1];		if(ans < d[idx][1])ans = d[idx][1];
	}		}
	cout<<ans;		cout<<ans;
Line 91:		Line 91:
	====		====
	[anniversary]		[anniversary]

imported>trailblaze at 16:46, 14 July 2014

2014-07-14T16:46:21Z

← Older revision		Revision as of 16:46, 14 July 2014
Line 89:		Line 89:
	return 0;		return 0;
	}		}
			====
			[anniversary]

imported>trailblaze at 16:45, 14 July 2014

2014-07-14T16:45:59Z

← Older revision		Revision as of 16:45, 14 July 2014
Line 10:		Line 10:
	* 각 노드(직원)에 대해서 파티에 참석할 때의 최대 친밀도와 참석하지 않을 때의 최대 친밀도를 구한다.		* 각 노드(직원)에 대해서 파티에 참석할 때의 최대 친밀도와 참석하지 않을 때의 최대 친밀도를 구한다.
	* 점화식		* 점화식
	d~~[~~idx~~][~~participate~~]~~ = sum_of_not_participate + intimaices~~[~~idx~~]~~;		d(idx,participate) = sum_of_not_participate + intimaices(idx);
	d~~[~~idx~~][~~participate~~]~~ = max(sum_of_participate, sum_of_not_participate);		d(idx,participate) = max(sum_of_participate, sum_of_not_participate);
	* DP 테이블을 채울 때는 leaf-node에서 root로 채워나가야 한다. -> 어떤게 leaf-node인지 판단하는게 필요.		* DP 테이블을 채울 때는 leaf-node에서 root로 채워나가야 한다. -> 어떤게 leaf-node인지 판단하는게 필요.

imported>trailblaze at 16:45, 14 July 2014

2014-07-14T16:45:17Z

New page

== 제출 결과 ==
run-id user id 프로그램 명 결과 언어 경과 시간(초) 코드 사이즈(byte) 제출 시간
1370542 zeropage anniversary accept C++ 0.04 2110 2014-07-15 01:06

== 풀이 ==

* 트리 구조를 반영하여 다이나믹을 구현해야 한다.
* leaf-node(부하가 없는 직원)부터 친밀도를 구하여 root까지의 친밀도를 구해야 한다.
* 직속 관계에 있는 직원들은 같이 파티에 참석하지 못한다. -> 트리의 부모가 파티에 참석하면, 자식은 파티에 참석하지 못한다. 자식이 하나라도 파티에 참석하면 부모는 파티에 참석하지 못한다. 로 해석이 가능.
* 각 노드(직원)에 대해서 파티에 참석할 때의 최대 친밀도와 참석하지 않을 때의 최대 친밀도를 구한다.
* 점화식
d[idx][participate] = sum_of_not_participate + intimaices[idx];
d[idx][participate] = max(sum_of_participate, sum_of_not_participate);
* DP 테이블을 채울 때는 leaf-node에서 root로 채워나가야 한다. -> 어떤게 leaf-node인지 판단하는게 필요.

== 소스 ==

#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
using namespace std;
const int N = 6020;
int n, intimacies[N];
int d[N][2]; // d[i][0] - participate, d[i][1] - not participate
int boss[N]; // at first, every staff's boss is himself. Thus boss[i] = i;
vector < list < int > > staffs; // vector[i]
vector < pair <int, int> > staff_priority_queue; // vector[i].first = level of Tree, vectors[i].second = idx.
int cmp(pair <int, int> s, pair <int, int> w){
return s.first > w.first;
}
void leveling_node(int node, int level){
staff_priority_queue[node].first = level;
for(list<int>::iterator it = staffs[node].begin(); it != staffs[node].end(); it++){
leveling_node(*it, level + 1);
}
}
int main(void){

cin>>n;
staff_priority_queue.resize(n + 10);
staffs.resize(n + 10);
staff_priority_queue[0].first = -1;
staff_priority_queue[0].second = -1;
for(int i = 1; i<=n; i++){
cin>>intimacies[i];
staff_priority_queue[i].second = i;
staff_priority_queue[i].first = -1;
boss[i] = i;
}
int L, k, m = 0;
while(1){
cin>>L>>k;
if(L == 0 && k == 0)break;
staffs[k].push_back(L);
staff_priority_queue[k].first++;
boss[L] = k;
//at the end, the root of subtree only satisfy 'boss[i] == i'.
m++;
};

if(n == m){
cout<<102;
return 0;
}//마지막 데이터 말도 안되는 거 처리를 위해서.. ()

for(int i = 1; i<=n; i++){
if(boss[i] == i){
leveling_node(i, 0);
}
}

int ans = -9999;
sort(staff_priority_queue.begin(), staff_priority_queue.begin() + n + 1, cmp);
//sorting by tree level.
for(int i = 0; i<n; i++){
int sum_of_participate = 0, sum_of_not_participate = 0;
int idx = staff_priority_queue[i].second;
for(list<int>::iterator it = staffs[idx].begin(); it != staffs[idx].end(); it++){
if(d[*it][0] >= 0)sum_of_participate += d[*it][0];
if(d[*it][1] >= 0)sum_of_not_participate += d[*it][1];
}
d[idx][0] = sum_of_not_participate + intimacies[idx];
d[idx][1] = max(sum_of_participate, sum_of_not_participate);
if(ans < d[idx][0])ans = d[idx][0];
if(ans < d[idx][1])ans = d[idx][1];
}
cout<<ans;
return 0;
}