글 읽기 - 1949번 우수 마을 데이터 추가요청입니다.

kkw564 7년 전 1

트리를 양방향이 아닌 단방향으로 보고 풀었는데 맞았습니다가 떴습니다.

이 코드에 대한 반례입니다. 원래는 답이 13000이어야 하는데 정답이 4000이 나오네요.

(아래 코드로 제출하니 AC가 떴습니다.)

7
1000 3000 4000 1000 2000 2000 7000
1 4
1 6
4 5
2 6
2 3
3 7

#include <cstdio>
#include <vector>
 
#define max(a,b)(a > b ? a : b)
#define swap(a,b){int t; t = a; a = b; b = t;} 
typedef long long int lli;

using namespace std;
 
int cost[10003];
vector <int> map[10003];
 
lli dy(int here, int i)
{
    lli ret = 0;
 
    for (int j = 0; j < map[here].size(); j++)
    {
        int next = map[here][j];
 
        // 현재 마을이 1(우수 마을)이라면 다음 마을은 우수 마을이 될 수 없다.
        if (i == 1)
            ret += dy(next, 0);
 
        // 현재 마을이 0(우수 마을 x)이라면 
        // 다음 마을은 우수 마을 or 우수 마을 x일 수 있다.
        else
            ret += max(dy(next, 0), cost[next] + dy(next, 1));
    }
 
    return ret;
}
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
        scanf("%d", &cost[i]);
 
 
    for (int i = 1; i<n; i++)
    {
        int from, to;
        scanf("%d %d", &from, &to);
 
        if (from > to)
            swap(from, to);
 
        map[from].push_back(to);
    }
 
    printf("%lld\n", max(dy(1, 0), cost[1] + dy(1, 1)));
 
    return 0;
}

cprayer 7년 전 1

트리의 독립집합(2213번)도 데이터 보강이 필요합니다.

제가 이 문제도 트리를 단방향으로 구성해서 풀었는데 둘 다 정답 처리됐었습니다.

baekjoon 7년 전 0

데이터 추가했습니다.

https://www.acmicpc.net/rejudg...

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

문제

문제

출처

ICPC

1949번 우수 마을 데이터 추가요청입니다.

kkw564 7년 전 1

cprayer 7년 전 1

baekjoon 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말