글 읽기 - O(N^2)

manybirds 5년 전 0

O(N)으로 구현했다고 생각했는데 시간초과가 나네요.

degree가 1인 ndoe부터 하나씩 제거하면서 edge가 나누는 node들의 최댓값 2개를 양방향으로 구하는 알고리즘입니다.

어디서 문제가 일어났는지 알고싶네요. 도와주세요!!

#include <iostream>
#include <vector>
#include <map>
#include <stack>
using namespace std;

int cost[1000001];
map<pair<int, int>, pair<int, int>> divmax;
int degree[1000001];
vector<int> T[1000001];
vector<int> A;
stack<int> S;

int main() {
    int N;
    cin >> N;
    int MAX = 0;
    for (int i=1; i<=N; i++) {
        cin >> cost[i];
        if (cost[i] > MAX) {
            MAX = cost[i];
        }
    }
    for (int i=0; i<N-1; i++) {
        int u, v;
        cin >> u >> v;
        degree[u]++;
        degree[v]++;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    for (int i=1; i<=N; i++) {
        if (degree[i] == 1) {
            A.push_back(i);
        }
    }
    /*
    for (int i=1; i<=N; i++) {
        cout << "Node : " << i << "degree : " << degree[i] << "connected : ";
        for (int v : T[i]) {
            cout << v << ' ';
        }
        cout << '\n';
    }
    for (int u : A) {
        cout << u << ' ';
    }
    */
    for (int i=0; i<N-1; i++) {
        int u = A.back();
        S.push(u);
        A.pop_back();
        int max = cost[u];
        int V;
        for (int v : T[u]) {
            if (degree[v] == 0) {
                if (divmax[make_pair(v, u)].first > max) {
                    max = divmax[make_pair(v, u)].first;
                }
            } else {
                degree[v]--;
                if (degree[v] == 1) {
                    A.push_back(v);
                }
                V = v;
            }
        }
        divmax.insert(make_pair(make_pair(u, V), make_pair(max, 0)));
        degree[u] = 0;
    }
    S.push(A.back());
    /*
    for (pair<pair<int, int>, pair<int, int>> p : divmax) {
        cout << p.first.first << ' ' << p.first.second << ' ' << p.second.first << ' ' << p.second.second << '\n'; 
    }
    cout << '\n';
    */
    while (!S.empty()) {
        //cout << S.top().first << ' ' << S.top().second << '\n';
        int u = S.top();
        int max1 = cost[u];
        int max2 = cost[u];
        for (int v : T[u]) {
            int w = divmax[make_pair(v, u)].first;
            if (w > max1) {
                max2 = max1;
                max1 = w;
            } else if (w > max2) {
                max2 = w;
            } 
        }
        for (int v : T[u]) {
            pair<int, int> p = divmax[make_pair(v, u)];
            if (p.first == max1) {
                p.second = max2;
            } else {
                divmax[make_pair(v, u)].second = max1;
            }
        }
        S.pop();
        //cout << divmax[make_pair(S.top().first, u)].second << '\n';
    }
    /*
    for (pair<pair<int, int>, pair<int, int>> p : divmax) {
        cout << p.first.first << ' ' << p.first.second << ' ' << p.second.first << ' ' << p.second.second << '\n'; 
    }
    */
    int max = 0;
    for (int u=1; u<=N; u++) {
        int sum = 0;
        for (int v : T[u]) {
            pair<int, int> p = divmax[make_pair(u, v)];
            if (p.first != 0 && p.second != 0) {
                sum += p.second;
            } else {
                sum += divmax[make_pair(v, u)].first;
            }
        }
        if (sum > max) {
            max = sum;
        }
    }
    cout << max;
    return 0;
}

BaaaaaaaaaaarkingDog 5년 전 0

코드를 자세히 보지는 않았는데 cin/cout 속도 때문은 아닐까요?

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

문제

문제

출처

ICPC

O(N^2)

manybirds 5년 전 0

BaaaaaaaaaaarkingDog 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말