글 읽기 - 시간초과 나는 이유 알려주세요 ㅠㅠ

san9407 5년 전 0

구글링 해보면 second max값이나 이진서치 이용해서 구하던데(lca에서 최대값 구하는 부분에 추가해서)

저는 위에것들 추가도 안했으니 오히려 계산은 적어야할거 같은데

계속 시간초과네요 ㅠㅠ

어디서 시간초과인지 알려주시면 감사하겠습니다!

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
const int INF = 1000000000;
const int MAX = 50000;

struct kruskal
{
	int from;
	int to;
	int val;
};

bool cmp(const kruskal& a, const kruskal& b)
{
	return a.val < b.val;
}

kruskal ks[MAX + 1];
vector<pair<int, int> > adj[MAX + 1];
int parent[MAX + 1];
bool visit[MAX + 1];
int dep[MAX + 1];
int par[20][MAX + 1];
int dist[20][MAX + 1];
bool check[4*MAX + 1];

int find(int x)
{
	if (parent[x] == x)
		return x;
	else
		return parent[x] = find(parent[x]);
}

bool merge(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y)
		return false;
	parent[x] = y;
	return true;
}

void dfs(int x)
{
	visit[x] = true;
	for (int i = 0; i < adj[x].size(); i++)
	{
		int next = adj[x][i].first;
		int cost = adj[x][i].second;
		if (!visit[next])
		{
			par[0][next] = x;
			dep[next] = dep[x] + 1;
			dist[0][next] = cost;
			dfs(next);
		}
	}
}

int lca(int u, int v)
{
	int ret = 0;
	if (dep[u] > dep[v])
		swap(u, v);
	for (int i = 19; i >= 0; i--)
	{
		int diff = dep[v] - dep[u];
		if (diff >= (1 << i))
		{
			ret = max(ret, dist[i][v]);
			v = par[i][v];
		}
	}
	if (u == v)
		return ret;
	for (int i = 19; i >= 0; i--)
	{
		if (par[i][u] != par[u][v])
		{
			ret = max(ret, max(dist[i][u], dist[i][v]));
			u = par[i][u];
			v = par[i][v];
		}
	}
	ret = max(ret, max(dist[0][u], dist[0][v]));
	return ret;
}

int main()
{
	int V,E;
	scanf("%d %d", &V,&E);
	for (int i = 0; i <= V; i++)
		parent[i] = i;
	for (int i = 0; i < E; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v,&w);
		ks[i].from = u;
		ks[i].to = v;
		ks[i].val = w;
	}
	sort(ks, ks + E, cmp);
	long long sum = 0;
	int cnt = 0;
	bool flag = false;
	for (int i = 0; i < E; i++)
	{
		int u = ks[i].from;
		int v = ks[i].to;
		int w = ks[i].val;
		if (merge(u, v))
		{
			check[i] = true;
			adj[u].push_back(make_pair(v, w));
			adj[v].push_back(make_pair(u, w));
			sum += w;
			cnt++;
			if (cnt == V - 1)
			{
				flag = true;
				break;
			}
		}
	}
	if (!flag || E==V-1)
	{
		puts("-1");
		return 0;
	}
	dfs(1);
	for (int i = 1; i < 20; i++)
	{
		for (int j = 1; j <= V; j++)
		{
			par[i][j] = par[i - 1][par[i - 1][j]];
			dist[i][j] = max(dist[i - 1][j], dist[i - 1][par[i - 1][j]]);
		}
	}
	long long maxx = 0x3f3f3f3f3f3f3f3f;
	for (int i = 0; i < E; i++)
	{
		if (check[i])
			continue;
		int u = ks[i].from;
		int v = ks[i].to;
		int w = ks[i].val;
		int t = lca(u, v);
		if (t == w)
			continue;
		maxx = min(maxx, (long long)(sum - t + w));
	}
	if (maxx == 0x3f3f3f3f3f3f3f3f || maxx == sum)
		puts("-1");
	else
		printf("%lld\n", maxx);
	return 0;
}

windflower 5년 전 0

find()함수가 부모 노드를 하나씩 검사하는 알고리즘이라면 시간복잡도가 O(V)가 되고 따라서 merge()함수도 시간복잡도가 O(V)가 되네요

그래서 main()함수 반복문에서 시간복잡도가 O(VE)가 되서 시간초과가 발생하는 것 같습니다!!

san9407 5년 전 0

find함수 parent[x] = find(parent[x]) 일경우 O(1)에 근접한거 아니였나요???

windflower 5년 전 0

tree에서 LCA 알고리즘 사용하였을 때 O(log n)으로 구할 수 있긴 하고 par[][]배열에서 LCA 알고리즘과 비슷한 방식으로 사용하신 것 같긴 한데...

parent배열에서는 이렇다 할 전처리과정이 보이지 않아서요

저 상태라면 부모노드를 2^k만큼 jump해서 찾는 것이 아니고 한칸씩 올라가면서 찾는 것이라 O(V)이 걸리지 않나요?

san9407 5년 전 0

find함수는 문제가 없어보이는게..

제가 여태까지 저 방식으로 MST문제를 다 푼걸로보아 find함수 문제는 아닌거 같습니다 ㅠㅠ

san9407 5년 전 0

찾았습니다.

크루스칼 배열크기도 잘못잡고 86번째줄도 오타가 있었네요..

이거 고치고 나니 역시나 WA..

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

문제

문제

출처

ICPC

시간초과 나는 이유 알려주세요 ㅠㅠ

san9407 5년 전 0

windflower 5년 전 0

san9407 5년 전 0

windflower 5년 전 0

san9407 5년 전 0

san9407 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말