글 읽기 - 메모리 초과가 납니다.

zxcv551133 6년 전 0

모든 index에 대해 go(index)가 O(n)번 호출 되게 짠것 같은데 어디를 잘못했는지 알려주시면감사하겠습니다.

#ifndef ONLINE_JUDGE
#define _CRT_SECURE_NO_WARNINGS
#endif // !ONLINE_JUDGE
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <math.h>
#include <bitset>
#include <set>
#include <map>
#include <queue>
#include <functional>
using namespace std;
const int I32MAX = 2147483647;
const vector<pair<int, int>> cardinalP = { { 0,1 },{ 0,-1 },{ -1,0 },{ 1,0 } };
// write below


int n, k;
vector<vector<int>> ar;
vector<int> d, cost;
int go(int index) {
	int &ret = d[index];
	if (ret != -1) return ret;
	if (ar[index].size() == 0) {
		return ret = cost[index];
	}
	for (int i = 0; i < ar[index].size(); i++) {
		ret = max(go(ar[index][i]), ret);
	}
	return ret = ret+cost[index];
}


int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif // !ONLINE_JUDGE
	cin.tie(0); ios_base::sync_with_stdio(0);
	//write your code below
	int tc; cin >> tc;
	while (tc--) {
		cin >> n >> k;
		ar.resize(n,vector<int>(0));
		d.assign(n, -1);
		cost.resize(n);

		for (int i = 0; i < n; i++) cin >> cost[i];
		for (int i = 0; i < k; i++) {
			int a, b; cin >> a >> b;
			ar[b-1].push_back(a-1);
		}
		int index; cin >> index;		
		cout << go(index-1) << '\n';
	}
	// code ended
	return 0;
}

djm03178 6년 전 1

46번째 줄이 문제인 것 같습니다. resize는 기존의 원소들은 그대로 남겨둔 채로 크기를 변경하는 거기 때문에 두 번째 케이스가 첫 번째 케이스보다 원소가 많은 경우에만 새 원소들이 vector<int>(0)으로 채워질 뿐, 기존 크기에 있던 것들은 그대로 남으니까요.

그 직전에 ar.clear(); 를 하니 맞게 나옵니다.

zxcv551133 6년 전 0

자체해결

46줄 앞에

ar.resize(0) 을 추가하니까 잘되네요

zxcv551133 6년 전 0

제가 댓글 쓰기 12초전에 댓글을 ㅋㅋ 감사합니다

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

문제

문제

출처

ICPC

메모리 초과가 납니다.

zxcv551133 6년 전 0

djm03178 6년 전 1

zxcv551133 6년 전 0

zxcv551133 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말