글 읽기 - 1167번 문제와 1967번 문제는 입력 형식만 다른 문제인가요?

silverfeather 2년 전 1

1967번 문제는 풀리는데 1167번 문제는 같은 코드로 틀렸습니다만 계속 뜨고 안풀리네요ㅜㅜ

입력 형식 말고는 같은 문제라고 생각하고 풀었는데 다른 점이 있나요?

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

void solve(std::vector<std::vector<std::pair<int, int>>> const &graph, std::vector<std::vector<std::pair<int, int>>> &midans, int const from, int const now) {
    
    int max=0, index=0;

    for ( int i=0; i<graph[now].size(); ++i ) {
        if (graph[now][i].first!=from && midans[now][i].second==-1) {
            solve(graph, midans, now, graph[now][i].first);
        }
    }

    if (from!=now) {
        index=0;
        while (graph[from][index].first!=now) { ++index; }
        for ( int i=0; i<midans[now].size(); ++i ) {
            if (max<midans[now][i].second) {
                max=midans[now][i].second;
            }
        }
        midans[from][index].second=max+graph[from][index].second;
    }

    return;
}

int main() {
    std::cin.tie(NULL);
    std::ios_base::sync_with_stdio(false);

    int v, in0, in1, in2, max0=0, max1=0, ans=0;
    std::vector<std::vector<std::pair<int, int>>> graph, midans;
    //std::vector<std::pair<int, std::pair<int, int>>> input;

    std::cin >> v;

    graph.resize(v);

    for ( int i=0; i<v; ++i ) {
        std::cin >> in0;
        std::cin >> in1;
        while (in1!=-1) {
            std::cin >> in2;
            graph[in0-1].push_back(std::make_pair(in1-1, in2));
            std::cin >> in1;
        }
    }

    for ( int i=0; i<v; ++i ) {
        std::sort(graph[i].begin(), graph[i].end());
    }

    // if (v==0) {
    //     std::cout << 0 << "\n";
    //     return 0;
    // }
    // if (v==1) {
    //     std::cout << 0 << "\n";
    //     return 0;
    // }
    // input.resize(v-1);

    // for ( int i=0; i<v-1; ++i ) {
    //     std::cin >> input[i].first >> input[i].second.first >> input[i].second.second;
    // }

    // graph.resize(v);
    // for ( int i=0; i<v-1; ++i ) {
    //     graph[input[i].first-1].push_back(std::make_pair(input[i].second.first-1, input[i].second.second));
    //     graph[input[i].second.first-1].push_back(std::make_pair(input[i].first-1, input[i].second.second));
    // }

    midans=graph;
    for ( int i=0; i<midans.size(); ++i ) {
        for ( int j=0; j<midans[i].size(); ++j ) {
            midans[i][j].second=-1;
        }
    }

    solve(graph, midans, 0, 0);
    
    // find ans from midans
    max0=0; max1=0;
    if (midans[0].size()==1) {
        ans=midans[0][0].second;
    }else {
        if (midans[0][0].second>=midans[0][1].second) {
            max0=midans[0][0].second;
            max1=midans[0][1].second;
        }else {
            max0=midans[0][1].second;
            max1=midans[0][0].second;
        }
        for ( int i=2; i<midans[0].size(); ++i ) {
            if (midans[0][i].second>=max0) {
                max1=max0;
                max0=midans[0][i].second;
            }else if (midans[0][i].second>max1) {
                max1=midans[0][i].second;
            }
        }
        ans=max0+max1;
    }
    for ( int i=1; i<midans.size(); ++i ) {
        max0=0; max1=0;
        if (midans[i].size()<=2) {
            continue;
        }else {
            if (midans[i][0].second>=midans[i][1].second) {
                max0=midans[i][0].second;
                max1=midans[i][1].second;
            }else {
                max0=midans[i][1].second;
                max1=midans[i][0].second;
            }
            for ( int j=2; i<midans[j].size(); ++j ) {
                if (midans[i][j].second>max0) {
                    max1=max0;
                    max0=midans[i][j].second;
                }else if (midans[i][j].second>max1) {
                    max1=midans[i][j].second;
                }
            }
            if (ans<max0+max1) {
                ans=max0+max1;
            }
        }
    }

    std::cout << ans << "\n";

    return 0;
}

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

문제

문제

출처

ICPC

1167번 문제와 1967번 문제는 입력 형식만 다른 문제인가요?

silverfeather 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말