글 읽기 - 17590번 틀렸습니다

jwpassion1 3년 전 0

공식 사이트 풀이를 보고 풀었고 열번이 넘게 잘못된 부분을 찾아 고쳤지만 여전히 틀렸습니다가 나옵니다. 일주일넘게 한문제만 붙들고있으려니까 코드도 잘 눈에 들어오지 않고 이대로면 문제 제출을 제가 다 채워버릴 것 같아서 틀린 부분을 찾아달라고 질문 올립니다.

풀이 링크 : 2019 ACM-ICPC North America Qualification Contest Solution Outlines (baylor.edu)

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

vector<vector<pair<int, int>>> tree;
vector<vector<int>> connecting;
vector<pair<int, int>> dp1;
vector<int> dp2;
int orb[200000], dist[200000], wh[200000];
bool including[200000], visited[200000];

void fi(int a, int b){
	for (const pair<int, int>& i : tree[a]){
		fi(i.first, a);
		if (including[i.first]){
			including[a] = true;
			wh[a] = i.first;
		}
	}
}

void f(int a, int b){
	if (visited[a]) return;
	visited[a] = true;
	if (orb[a] < 0){
		dp1[a] = { dist[a], 2000000000 };
		tree[a].clear();
		return;
	}
	if (including[a]){
		priority_queue<pair<int, int>> que;
		for (const pair<int, int>& i : tree[a]){
			if (i.first == wh[a]) que.push({ -i.second, 2000000000 });
			else{
				f(i.first, a);
				que.push({ -dp1[i.first].first, i.first });
			}
		}
		int neeed = dist[a], have = orb[a];
		while (!que.empty()){
			pair<int, int> c = que.top();
			que.pop();
			c.first = -c.first;
			if (c.second == 2000000000) break;
			if (dp1[c.second].second <= 0) continue;
			if (c.first > have){
				neeed += c.first - have;
				have = 0;
			}
			else{
				have -= c.first;
			}
			have += dp1[c.second].second + c.first;
			for (const int& i : connecting[c.second]){
				f(i, a);
				que.push({ -dp1[i].first, i });
			}
			connecting[c.second].clear();
		}
		while (!que.empty()){
			tree[wh[a]].push_back({ que.top().second, dist[que.top().second] });
			que.pop();
		}
		f(wh[a], a);
		if (max(dp1[wh[a]].first, dist[wh[a]]) > have){
			neeed += max(dp1[wh[a]].first, dist[wh[a]]) - have;
		}
		dp1[a] = { neeed, 2000000000 };
		tree[a].clear();
		return;
	}
	if (orb[a] > dist[a]){
		dp1[a] = { dist[a], orb[a] - dist[a] };
		for (const pair<int, int>& i : tree[a]){
			connecting[a].push_back(i.first);
		}
		tree[a].clear();
		return;
	}
	int neeed = dist[a], have = orb[a];
	priority_queue<pair<int, int>> que;
	for (const pair<int, int>& c : tree[a]){
		f(c.first, a);
		que.push({ -dp1[c.first].first, c.first });
	}
	while (!que.empty()){
		pair<int, int> c = que.top();
		que.pop();
		c.first = -c.first;
		if (dp1[c.second].second <= 0) continue;
		if (c.first > have){
			neeed += c.first - have;
			have = 0;
		}
		else{
			have -= c.first;
		}
		have += dp1[c.second].second + c.first;
		for (const int& i : connecting[c.second]){
			f(i, a);
			que.push({ -dp1[i].first, i });
		}
		connecting[c.second].clear();
		if (have > neeed) break;
	}
	if (have <= neeed){
		dp1[a] = { 2000000000, -1 };
		tree[a].clear();
		return;
	}
	while (!que.empty()){
		connecting[a].push_back(que.top().second);
		que.pop();
	}
	dp1[a] = { neeed, have - neeed };
	tree[a].clear();
}

void g(int a, int b){
	if (orb[a] >= 0) dp2[a] = dist[a] - orb[a];
	else dp2[a] = dist[a];
	for (const pair<int, int>& i : tree[a]){
		g(i.first, a);
		dp2[a] += dp2[i.first];
	}
	if (!including[a]) dp2[a] = max(dp2[a], dist[a] - 1);
	else dp2[a] = max(dp2[a], dist[a]);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, p, o, d;
	cin >> n;
	dp2.resize(n);
	dp1.resize(n);
	connecting.resize(n);
	tree.resize(n);
	for (int i = 1; i < n; i++){
		cin >> p >> o >> d;
		tree[p].push_back({ i, d });
		orb[i] = o;
		dist[i] = d;
		if (o < 0) including[i] = true;
	}
	fi(0, -1);
	g(0, -1);
	f(0, -1);

	cout << dp2[0] << ' ' << dp1[0].first;

	return 0;
}

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

문제

문제

출처

ICPC

17590번 틀렸습니다

jwpassion1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말