글 읽기 - 1005번 문제 어디가 틀렸을까요....

hyseokim 6년 전 0

33퍼센트 에서 틀렸다고 나오는데 반례를 도저히 못찾겠네요....

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int testcase, building_num, q, res;
vector <long long int> build_time;
vector <vector<int>> edge1;
vector <vector<int>> edge2;
vector <int> ind;
void cal() {
	queue <int> q;
	
	for (int i = 1; i <= building_num; i++) {
		if (ind[i] == 0)
			q.push(i);
	}
	while (!q.empty()) {
		int here = q.front();
		q.pop();

		for (int i = 0; i < edge1[here].size(); i++) {
			int there = edge1[here][i];
			ind[there]--;
			if (ind[there] == 0) {
				q.push(there);
				long long int max = 0;
				for (int j = 0; j < edge2[there].size(); j++) {
					int pre=edge2[there][j];
					if (max < build_time[pre]) {
						max = build_time[pre];
					}
				}
				build_time[there] += max;
				if (there == res) {
					cout << build_time[there] << endl;
					return;
				}
			}
		}
	}
}
int main() {
	cin >> testcase;

	for (int t = 0; t < testcase; t++) {
		cin >> building_num >> q;
		edge1.resize(building_num + 1);
		edge2.resize(building_num + 1);
		ind.resize(building_num + 1, 0);
		build_time.resize(building_num + 1);
		for (int i = 1; i <= building_num; i++) {
			cin >> build_time[i];
		}
		for (int i = 0; i < q; i++) {
			int b1, b2;
			cin >> b1 >> b2;
			ind[b2]++;
			edge1[b1].push_back(b2);
			edge2[b2].push_back(b1);
		}
		cin >> res;
		cal();
	}

	return 0;
}

djm03178 6년 전 1

다음을 고치니 맞았습니다.

1. resize는 기존의 내용물을 버리지 않습니다. 즉, 이전 테스트케이스에서 사용되었던 edge1, edge2, ind 값이 모두 그대로 남아있는 상태에서 다음 케이스를 진행하기 때문에 문제가 됩니다. 매 케이스 시작 때 전부 clear() 를 해주면 됩니다.

2. 답을 출력하는 부분이 there에서 발견했을 때 뿐인데, 이전에 지어야 하는 건물이 하나도 없는 경우에는 아무 답을 출력하지 않는 문제가 발생합니다. 따라서 there가 아닌 here에서 발견했을 때 출력해야 맞습니다.

hyseokim 6년 전 0

정말 감사합니다!!!!!

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

문제

문제

출처

ICPC

1005번 문제 어디가 틀렸을까요....

hyseokim 6년 전 0

djm03178 6년 전 1

hyseokim 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말