글 읽기 - 11960번 max flow (hld,+lazy,c++)

wnsduds1 2년 전 0

hld알고리즘을 이용해서 단순경로에 있는 값들을 lazy하게 update했습니다!

업데이트 되는 부분에서 최대값만을 갱신하면서 답을 구해보고 있는데 애초에 tle가 나는군요..

https://www.acmicpc.net/proble...

https://www.acmicpc.net/submit...

농장관리 문제와 비슷하게 로직을 짰습니다.

하지만 농장관리는 통과가 되었는데 max flow는 통과가 안되네요..

일전에도 top-down방식의 세그먼트를 이용한 hld알고리즘은 tle가 나서 bottom-up방식으로 hld문제를 해결하곤했는데요..

시간복잡도는 O(log(n)^2*m)이라고 생각합니다..

거두절미하고

1.O(log(n)^2*m)코드가 TLE가 나는 이유가 궁금합니다.!

2. 농장관리 코드와 max flow코드는 동작하는 원리가 거의 동일합니다. 하지만 농장관리는 ac이고 max flow 는 tle인지 궁금합니다.

제가 놓치고 있거나 잘못알고있는 점이 있다면 알려주세요!

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define SIZE 50001
using namespace std;
vector<int>adj[SIZE];
int n;
int ret = 0;
struct seg {
	int tree[4 * SIZE] = { 0, }, lazy[4 * SIZE] = { 0, };
	seg() : tree() {
	}
	void propaganda(int node, int start, int end) {
		if (lazy[node]) {
			tree[node] += lazy[node];
			ret = max(ret, tree[node]);
			if (start != end) {
				lazy[node * 2] += lazy[node];
				lazy[node * 2 + 1] += lazy[node];
			}
			lazy[node] = 0;
		}
	}
	void update(int node, int start, int end, int left, int right) {
		propaganda(node, start, end);
		if (start > right || end < left)return;
		else if (left <= start && end <= right) {
			tree[node] += 1;
			ret = max(ret, tree[node]);
			if (start != end) {
				lazy[node * 2] += 1;
				lazy[node * 2 + 1] += 1;
			}
		}
		else {
			int pit = (start + end) / 2;
			update(node * 2, start, pit, left, right);
			update(node * 2 + 1, pit + 1, end, left, right);
			tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
		}
	}
	int query(int node, int start, int end, int left, int right) {
		propaganda(node, start, end);
		if (start > right || end < left)return 0;
		else if (left <= start && end <= right) {
			return tree[node];
		}
		else {
			int pit = (start + end) / 2;
			return max(query(node * 2, start, pit, left, right), query(node * 2 + 1, pit + 1, end, left, right));
		}
	}


};
struct hld {
	int top[SIZE], sub[SIZE], level[SIZE], par[SIZE], in[SIZE];
	int innate = 0;
	hld() :sub(), par(), in() {
		for (int i = 1; i <= n; i++) {
			top[i] = i;
		}
	}
	int dfs(int v = 1, int parent = 0) {
		sub[v] = 1;
		par[v] = parent;
		level[v] = level[parent] + 1;
		for (auto &nxt : adj[v]) {
			if (nxt != parent) {
				sub[v] += dfs(nxt, v) + 1;
			}
		}
		return sub[v];
	}
	void dfs1(int v = 1, int parent = 0) {
		int flag = 0;
		for (int i = 0; i < adj[v].size(); i++) {
			if (adj[v][i]== parent)flag = 1;
			else {
				if (sub[adj[v][flag]] < sub[adj[v][i]]) {
					swap(adj[v][flag], adj[v][i]);
				}
				dfs1(adj[v][i], v);
			}
		}
	}
	void dfs2(int v = 1, int parent = 0) {
		in[v] = ++innate;;
		int flag = 0;
		for (auto &nxt : adj[v]) {
			if (nxt != parent) {
				if (flag == 0) {
					top[nxt] = top[v];
					flag = 1;
				}
				dfs2(nxt, v);
			}
		}
	}
	void path_update(seg &s, int v1, int v2) {
		int ret = 0;
		while (top[v1] != top[v2]) {
			if (level[top[v1]] > level[top[v2]]) {
				s.update(1, 1, n, in[top[v1]], in[v1]);

				v1 = par[top[v1]];
			}
			else {
				s.update(1, 1, n, in[top[v2]], in[v2]);
				v2 = par[top[v2]];
			}
		}
		if (level[v1] > level[v2]) {
			s.update(1, 1, n, in[v2], in[v1]);
		}
		else {
			s.update(1, 1, n, in[v1], in[v2]);
		}
	}
	int  path_qeury(seg &s, int v1, int v2) {
		int ret = 0;
		while (top[v1] != top[v2]) {
			if (level[top[v1]] > level[top[v2]]) {
				ret = max(ret, s.query(1, 1, n, in[top[v1]], in[v1]));

				v1 = par[top[v1]];
			}
			else {
				ret = max(ret, s.query(1, 1, n, in[top[v2]], in[v2]));
				v2 = par[top[v2]];
			}
		}
		if (level[v1] > level[v2]) {
			ret = max(ret, s.query(1, 1, n, in[v2], in[v1]));
		}
		else {
			ret = max(ret, s.query(1, 1, n, in[v1], in[v2]));
		}
		return ret;
	}

};
int main() {
	fastio;
	int m, v1, v2;
	cin >> n >> m;
	for (int i = 0; i < n - 1; i++) {
		cin >> v1 >> v2;
		adj[v1].push_back(v2);
		adj[v2].push_back(v1);
	}
	seg s;
	hld h;
	h.dfs();
	h.dfs1();
	h.dfs2();
	for (int i = 0; i < m; i++) {
		cin >> v1 >> v2;
		h.path_update(s, v1, v2);
	}
	cout << ret;

	return 0;
}

slah007 2년 전 1

가장 큰 문제는 hld가 제대로 이루어지지 않아 어떤 vertex v에 대해 v->root 경로 상에 decomposion의 chain이 O(log n)개만 있음이 보장되지 않습니다. 상수도 숭요하게 생각한다면 range update point query는 lazy segment tree가 필요 없기도 합니다.

또한, 이 문제는 hld에 익숙하다면 그냥 대입하는게 편하긴 하지만 hld 이외의 풀이도 있습니다.

USACO는 test data와 solution을 다 제공하므로 그걸로 디버깅을 하면 편합니다. http://www.usaco.org/index.php...

wnsduds1 2년 전 0

답변 정말 감사합니다.

decomposion의 chain이 O(log n)개만 있음이 보장되지 않는 코드일 줄을 전혀몰랐네요..

다시 공부를 해야겠어요 !

정말 감사드립니다.

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

문제

문제

출처

ICPC

11960번 max flow (hld,+lazy,c++)

wnsduds1 2년 전 0

slah007 2년 전 1

wnsduds1 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말