글 읽기 - 시간 초과가 계속 뜨네요.... 어떻게 해야 시간을 개선 할 수 있을까요?

parkpkww 4년 전 1

타잔 알고리즘으로 SCC들을 구하고,

이후 각 SCC 들 간의 tree를 구성한 뒤,

start 지점이 포함된 SCC 를 시작으로 자식 SCC 들을 돌면서 정답을 갱신해주었습니다.

SCC 구성에 O(V+E) + 트리따라 가면서 정답 갱신에 O(V) 라고 생각하고 풀었는데 계속 시간초과가 나네요... ㅠ

혹시 문제점이나 개선할 수 있는 방법이 있을까요...?

#include <bits/stdc++.h>
using namespace std;
const int MAX = 500001;
typedef long long ll;

int N, M, cnt, SN, S, P;
vector<int> adj[MAX];
int dfsn[MAX], sn[MAX], price[MAX];
stack<int> SS;
bool finished[MAX], hasrest[MAX];

ll SSCprice[MAX];
bool SSChasrest[MAX];
set<int> arr[MAX];
ll ans;

int DFS(int curr){ // SCC 구성
    dfsn[curr] = ++cnt;
    SS.push(curr);
    int result = dfsn[curr];
    for (int next: adj[curr]){
        if(dfsn[next]==0) result = min(result, DFS(next));
        else if(!finished[next]) result = min(result, dfsn[next]);
    }

    if(result == dfsn[curr]){
        while(1){
            int t = SS.top();
            SS.pop();
            finished[t] = true;
            sn[t] = SN;
            SSCprice[SN]+=price[t];  // 각 SCC들이 갖고 있는 돈의 합
            if(hasrest[t]) SSChasrest[SN] = true;  // 레스토랑이 있는 SCC 체크
            if(t==curr) break;
        }
        SN++; // 각 SCC 들의 번호
    }
    return result;
}

void findans(int a, ll temp){ // 트리(?)따라 내려가기
    temp += SSCprice[a];
    if(SSChasrest[a]) ans = max(ans, temp); // 레스토랑이 있는 SCC 에서 정답을 갱신
    for (int next: arr[a]){
        findans(next,temp);
    }
}

int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE

cin >> N >> M;

for (int i = 0; i < M; ++i){
    int A, B;
    cin >> A >> B;
    adj[A].push_back(B);
}

for (int i = 1; i<=N; ++i) 
    cin >> price[i];

cin >> S >> P;
for (int i = 0; i < P; ++i){
    int p;
    cin >> p;
    hasrest[p] = true;
}
for (int i = 1; i <= N; ++i)
    if(dfsn[i]==0) DFS(i);

// SCC의 tree(?)를 set으로 구성, 즉 각 SCC가 자식들을 set으로 갖고있게 만듬 
for (int i = 1; i <= N; ++i){
    for(int j: adj[i]){
        if(sn[i]!=sn[j]) arr[sn[i]].insert(sn[j]);
    }
}

findans(sn[S],0); // start 지점에서 시작

cout << ans << '\n';


return 0;
}

parkpkww 4년 전 1

최대값을 내려가는 findans 함수를 dp로 풀었더니 풀렸습니다.

ll findans(int a){
    ll temp = 0;
    ll &ret = dp[a];
    if(ret!=-1) return ret;
    for (int next: arr[a]){
        temp = max(temp, findans(next));
    }
    if(temp == 0){
        if(!SSChasrest[a]) return ret = 0;
        else return ret = SSCprice[a];
    }
    else
        return ret = temp + SSCprice[a];
}

parkpkww 3년 전 0

아... 그런 방법이 있네요!

정말 감사합니다!

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

문제

문제

출처

ICPC

시간 초과가 계속 뜨네요.... 어떻게 해야 시간을 개선 할 수 있을까요?

parkpkww 4년 전 1

parkpkww 4년 전 1

parkpkww 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말