글 읽기 - LCA 느낌으로 푸는 문제 아닌가요??

147_369 3년 전 0

정말 열심히 짰는데 자꾸 26% 쯤에서 틀리네요.... 혹시 조언 주실 분 계신가요...ㅠㅠㅠㅠㅠ

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define pii pair<int, int>
#define ll long long

// 개미 방의 개수
int N;
// i번째 방에 있는 개미의 에너지
int energy[100001];
// 인접리스트
vector<pii> adj[100001];
// i번째 방의 깊이(1번방을 깊이 1)
int depth[100001];
// 2^k번째 부모방의 정보(부모방 번호와 필요한 비용)
pii dp[18][100001];


void init() {
    scanf("%d", &N);
    for (int i=1; i<=N; i++) {
        scanf("%d", &energy[i]);
        depth[i] = -1;
    }
    depth[0] = 0;
    for (int i=1, a, b, w; i<N; i++) {
        scanf("%d%d%d", &a, &b, &w);
        adj[a].push_back(pii(b, w));
        adj[b].push_back(pii(a, w));
    }
    return;
}

// depth배열 채우는 dfs
void find_depth(int now, int pre) {
    depth[now] = depth[pre]+1;
    if (now==N) {
        return;
    }
    for (int i=0, dest; i<adj[now].size(); i++) {
        dest = adj[now][i].first;
        if (depth[dest]==-1) {
            find_depth(dest, now);
        }
    }
    return;
}

// LCA 정보 채우기
void fill_dp() {
    dp[0][1].first = 1;
    dp[0][1].second = 0;
    for (int i=1; i<=N; i++) {
        for (int j=0, dest, cost; j<adj[i].size(); j++) {
            dest = adj[i][j].first;
            cost = adj[i][j].second;
            if (depth[dest]>depth[i]) {
                dp[0][dest] = pii(i, cost);
            }
        }
    }
    for (int i=1; i<18; i++) {
        for (int j=1; j<=N; j++) {
            dp[i][j].first = dp[i-1][dp[i-1][j].first].first;
            dp[i][j].second = dp[i-1][dp[i-1][j].first].second + dp[i-1][j].second;
        }
    }
    return;
}

// 최종 목적지 찾기
int find_dest(int now) {
    int last_energy = energy[now];
    for (int i=17; i>=0; i--) {
        if (dp[i][now].second<=last_energy) {
            last_energy -= dp[i][now].second;
            now = dp[i][now].first;
            if (now==1 || last_energy==0) {
                return now;
            }
        }
    }
    return now;
}

// 풀이 함수
void solve() {
    init();
    find_depth(1, 0);
    fill_dp();
    for (int i=1, ans; i<=N; i++) {
        ans = find_dest(i);
        printf("%d\n", ans);
    }
    return;
}

int main () {
    solve();
    /*for (int j=0; j<18; j++) {
        for (int i=1; i<=N; i++) {
            printf("cur:%d / order:%d / parent:%d / weight:%d / energy:%d\n", i, j, dp[j][i].first, dp[j][i].second, energy[i]);
        }
        printf("#################################\n");
    }*/
    return 0;
}

rootsquare 1년 전 0

최대로 올라갈 수 있는 방을 구하는 문제입니다. DFS를 활용해서 각 방별로 도달하는데 지나야 하는 방들을 스택에 넣어보세요. 그럼 다른 접근이 보일 것입니다

(LCA로 푸는 문제 아닙니다!)

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

문제

문제

출처

ICPC

LCA 느낌으로 푸는 문제 아닌가요??

147_369 3년 전 0

rootsquare 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말