글 읽기 - TLE 나는 이유를 모르겠습니다.

iriszero 8년 전 0

cash에 넣으면서 정방향 역방향 탐색했는데 왜 TLE가 날까요?

#include <stdio.h>
#include <vector>
#include <algorithm>

#define INF 987654321
#define MX 100
using namespace std;

int dfs(int idx, const vector<vector<int>>& graph, vector<int>& cash) {
	
	int &ret = cash[idx];
	if (ret > 0) return ret;
	ret = 1;

	for (auto nxt : graph[idx]) {
		ret += dfs(nxt, graph, cash);
	}

	return ret;
}
int main(void) {
	int N, M; scanf("%d %d", &N, &M);
	vector<vector<int>> graph, inv_graph;
	graph.resize(N);
	inv_graph.resize(N);

	vector<int> a_cnt(N, 0), b_cnt(N, 0);
	while (M--){
		int src, dst; scanf("%d %d", &src, &dst);
		src--; dst--;
		graph[src].push_back(dst);
		inv_graph[dst].push_back(src);
	}

	int ans = N;
	for (int i = 0; i < N; i++) {
		
		if (dfs(i, graph, a_cnt) <= (N - 1) / 2
			&& dfs(i, inv_graph, b_cnt) <= (N - 1) / 2) {
			ans--;
		}
	}

	printf("%d\n", ans);
}

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

문제

문제

출처

ICPC

TLE 나는 이유를 모르겠습니다.

iriszero 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말