글 읽기 - dfs 문제 시간초과 가 나는데 줄일 수 있는 방법이 안떠오르네요

jjh4698 8년 전 0

처음에는 2차원 벡터로 안하고 N으로 하였다가 시간초과가 나서 2차원 벡터로 받았는데도 시간 초과가 나네요..

시간 줄일 수 있는 방법이 있을까요?

꼭 도움 부탁드립니다.. ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <string.h>

using namespace std;
int N, M;
int pay[500001];
int boss[500001];
bool check[500001];
vector<vector<int > > v;

void dfs(int A, int increase)   // A의 부하직원의 봉급을 올린다.
{
	for (int i = 0; i < v[A].size(); i++)
	{
		if (check[v[A][i]] == false)
		{
			pay[v[A][i]] += increase;
			check[v[A][i]] = true;
			dfs(v[A][i], increase);
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	char str[2];
	int A, increase,x;
	scanf("%d %d", &N, &M);
	v.resize(N + 1);
	boss[1] = 0;
	scanf("%d", &pay[1]);
	for (int i = 2; i <= N; i++)
	{
		scanf("%d %d", &pay[i], &x);
		v[x].push_back(i);			// x의 부하는 i들이다.
	}
	for (int i = 1; i <= M; i++)
	{
		scanf("%s", str);
		if (str[0] == 'p')
		{
			scanf("%d %d", &A, &increase);
			memset(check, false, sizeof(check));
			dfs(A, increase); // A의 부하직원들의 봉급을 올려라.
		}
		else if (str[0] == 'u')
		{
			scanf("%d", &A);
			printf("%d\n", pay[A]);
		}
	}
}

baactree 8년 전 1

그냥 O(NM)에 푸신거같은데

jjh4698 8년 전 0

좀더 줄일수 있는 방법이 있을까요??

지금 생각하는 방법은 저장할때 가장 높은 상사에게 부하직원 정보가 전부 들어가게 입력해서

for문을 한 직원 만큼만 돌리는거인데..

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

문제

문제

출처

ICPC

dfs 문제 시간초과 가 나는데 줄일 수 있는 방법이 안떠오르네요

jjh4698 8년 전 0

baactree 8년 전 1

jjh4698 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말