글 읽기 - 1005 ACM craft 시간초과도 아니고 틀렸습니다가 나옵니다

jh1125kr 7년 전 0

이 문제를 결론적으로 말하면 dfs+dp로 해서 맞았긴했는데,

dfs로만 풀었던 방법이 시간초과도 아니고 틀렸습니다가 나와서 의문입니다.

일단 아래처럼 dfs+dp로 풀어서 맞았고

int dfs(int cur) {
    int cur_size = adj[cur].size();
    int &ret = dp[cur];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = 0; i < cur_size; i++) {
        int next_v = adj[cur][i];
        ret = max(dfs(next_v), ret);
    }
    return ret = dp[cur] + building[cur];
}

dp를 적용하지 않았던 방법으로는 소스코드 처럼 풀었는데요...

시간초과나 스택오버플로우인 런타임에러는 이해가지만

왜 틀렸는지는 모르겠습니다..ㅠㅠ

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<memory.h>
#define N 1000
using namespace std;
 
vector<int> adj[N + 1];
int building[N + 1];
int visited[N + 1];
 
int dfs(int cur) {
    int cur_size = adj[cur].size();
    int mx = 0;
    for (int i = 0; i < cur_size; i++) {
        int next_v = adj[cur][i];
        if (visited[next_v] != 0) {
            visited[next_v]--;
            mx = max(dfs(next_v), mx);
        }
    }
    return mx+building[cur];
}
int main()
{
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        for (int j = 1; j <= N; j++) {
            adj[j].clear();
            visited[j] = 0;
        }
        int n, m, a, b, k;
        scanf("%d %d", &n, &m);
        for (int j = 1; j <= n; j++) {
            scanf("%d", &building[j]);
        }
        for (int j = 0; j < m; j++) {
            scanf("%d %d", &a, &b);
            adj[b].push_back(a);
            visited[a]++;
        }
        scanf("%d", &k);
        printf("%d\n",dfs(k));
    }
}

jh1125kr 7년 전 0

해결했습니다.

10 11
10 1 1 100 10 10 100 1 1 1
1 2
2 3
3 6
4 3
4 7
4 9
5 4
6 9
7 8
8 9
10 7
9

이케이스에서 잘못된 값이 나왔습니다

allen246 2년 전 0

좋은 반례네요! 감사합니다

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

문제

문제

출처

ICPC

1005 ACM craft 시간초과도 아니고 틀렸습니다가 나옵니다

jh1125kr 7년 전 0

jh1125kr 7년 전 0

allen246 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말