글 읽기 - 40%에서 메모리 초과 뜹니다...

wotnd00 5년 전 0

merge_tree[i] 는 i노드를 루트로 하는 트리의 모든 노드들을 색깔 순대로 정렬 해놓은 vector입니다.

문제가 주어지면 노드 번호에 맞는 meger_tree를 주어진 문제의 색깔에 맞게 이분탐색을 합니다.

그런데 40%에서 메모리 초과 뜨는데,,, 다른 방법을 잘 모르겠습니다...ㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>


using namespace std;

int n,m,c;

int Answer;



vector<int> col;
vector<int> visit;
vector<int> tree;
vector<vector<int>> map;
vector<vector<pair<int, int>>> merge_tree;

bool cmp(pair<int, int> &a, pair<int, int> &b)
{
	return a.second < b.second;
}

void dfs(int k)
{
	visit[k] = 1;
	tree.push_back(k);
	int start = tree.size() - 1;

	for (int i = 0; i < map[k].size(); i++)
		if (visit[map[k][i]] == 0)
			dfs(map[k][i]);

	int end = tree.size();
	for (int i = start; i < end; i++)
		merge_tree[k].push_back(make_pair(tree[i],col[tree[i]]));
	return;
}




int go(vector<pair<int,int>> &s,int k)
{
	int max = -1;
	int  left = 0;
	int right = s.size() - 1;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (s[mid].second <= k)
		{
			if (max < mid)
				max = mid;
			left = mid + 1;
		}
		else
			right = mid - 1;
	}

	return max+1;
}


int main(void)
{
	cin >> n >> m >> c;

	col = vector<int>(n + 1);
	visit=vector<int>(n + 1);
	map = vector<vector<int>>(n + 1);

	merge_tree = vector<vector<pair<int, int>>>(n + 1);

	for (int i = 1; i <= n; i++)
		scanf("%d", &col[i]);

	for (int i = 0; i < n - 1; i++)
	{
		int x, y;
		cin >> x >> y;
		map[x].push_back(y);
		map[y].push_back(x);
	}

	dfs(1);
	visit.clear();
	map.clear();
	col.clear();

	for (int i = 1; i <= n; i++)
		sort(merge_tree[i].begin(), merge_tree[i].end(),cmp);

	for (int i = 0; i < m; i++)
	{
		int count = 0;
		int v, c;
		scanf("%d %d", &v, &c);
		count = go(merge_tree[v], c);
		Answer = (Answer + count) % 10000000007;

	}

	printf("%d\n", Answer);
	return 0;
}

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

문제

문제

출처

ICPC

40%에서 메모리 초과 뜹니다...

wotnd00 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말