27355 Paths

문제는 간단합니다. 수족관을 모든 정점에서 계산하면 됩니다.

 

당연히 모든 정점에서 다시 DFS를 하면 TLE가 뜹니다. 그렇기 때문에 값을 재활용하는 것을 생각해 볼 수 있습니다.

 

$1$번 정점에서 DFS를 해서 나오는 $pq$와, 그 정점과 인접해있는 $2$번 정점에서의 $pq$의 차이를 생각해봅시다. 사실, $1$번 $pq$에서 $2$개의 원소를 넣고, $2$개의 원소를 빼면 $2$번 $pq$가 됩니다.

넣고 빼는 원소는 미리 리루팅 DFS를 이용해 구해줄 수 있습니다.

그 후는 DFS를 한번 더 하면서, $pq$를 그 루트 그대로 데려가주면 됩니다.

정확히는 $삽입 / 삭제 / 상위 K개 원소 합$ 연산을 수행할 수 있는 새로운 자료구조를 하나 만들면 됩니다.

이는 $multiset$을 이용하면 쉽게 구현할 수 있습니다.

구현 팁으로는, $rollback$연산도 만들어두면 마지막에 순회할 때 쉬워집니다.

 

struct ULTIMATE_P_Q {
	multiset<ll> seK;
	multiset<ll> seNOKO;
	ll SUM = 0;

	stack<pair<bool ,ll>> stk;

	void ADD(ll x) {
		stk.ps({1, x});
		if (x==0) return;
		if (seK.size() < K) {
			seK.is(x);
			SUM += x;
		} else {
			auto itit = seK.begin();
			if ((*itit) < x) {
				seNOKO.is(*itit);
				SUM -= *itit;
				seK.erase(itit);
				seK.is(x);
				SUM += x;
			} else {
				seNOKO.is(x);
			}
		}
		return;
	}

	void ERASE(ll x) {
		stk.ps({0, x});
		if (x==0) return;
		auto itit = seK.find(x);
		if (itit != seK.end()) {
			seK.erase(itit);
			SUM -= x;
			if (!seNOKO.empty()) {
				auto it = prev(seNOKO.end());
				SUM += *it;
				seK.is(*it);
				seNOKO.erase(it);
			}
		} else {
			seNOKO.erase(seNOKO.find(x));
		}
		return;
	}

	void rollback() {
		ll T = 4;
		while (T--) {
			auto [bb, x] = stk.top();
			stk.pop();
			if (bb) {
				ERASE(x);
			} else {
				ADD(x);
			}
			stk.pop();
		}
		return;
	}
} PQ;

 

제 구조체입니다.