백준 12745번: Traffic (Small) (C++)

https://www.acmicpc.net/problem/12745

12745번: Traffic (Small)

---

Solved By: LCA (using Sparse Table)

 

시간 복잡도 상으로는 시간 초과가 나와야할 거 같은 코드가 맞았습니다.

 

section배열을 선언하여 a, b사이를 얼마나 지나갔는지 저장하였습니다.

트리의 구조이기도 하고, 모든 사람들이 최단 거리로 이동했기 때문에 LCA를 사용했습니다.

쿼리에서 lcaNode를 구하여 a에서 lcaNode까지 한 칸씩 이동하며 각 구간의 거리를 지나갔음을 알려주었습니다.

b에서 lcaNode도 마찬가지입니다.

>> 이부분에서 lcaNode까지 한 칸씩 이동하는 과정이 시간 초과가 걸릴 줄 알았습니다.

>> 왜냐하면 lca를 구하는 건 O(logN)이지만 이동하는 과정은 O(N)이라 O(Q*N)이 발생하기 때문입니다.

 

#include <iostream>
#include <vector>
#define MAX 2223
#define LOG_MAX 12
using namespace std;

int parent[MAX][LOG_MAX];
int level[MAX];
vector<int> adj[MAX];
int section[MAX][MAX];
int n, q;

void dfs(int now, int par){
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(next == par) continue;
        
        parent[next][0] = now;
        level[next] = level[now] + 1;
        
        dfs(next, now);
    }
}

void swap(int* a, int* b){
    int* temp = a;
    a = b;
    b = temp;
}

int lca(int a, int b){
    if(level[a] < level[b]) swap(a, b);
    
    int diff = level[a] - level[b];
    
    for(int i = LOG_MAX - 1; i >= 0; i--){
        if(diff >= 1 << i){
            diff -= 1 << i;
            a = parent[a][i];
        }
    }
    
    if(a != b){
        for(int i = LOG_MAX - 1; i >= 0; i--){
            if(parent[a][i] != 0 && parent[a][i] != parent[b][i]){
                a = parent[a][i];
                b = parent[b][i];
            }
        }
        
        a = parent[a][0];
    }
    
    return a;
}

void prefixSum(int a, int b, int lcaNode){
    while(a != lcaNode){
        section[a][parent[a][0]]++;
        section[parent[a][0]][a]++;
        a = parent[a][0];
    }
    
    while(b != lcaNode){
        section[b][parent[b][0]]++;
        section[parent[b][0]][b]++;
        b = parent[b][0];
    }
}

int main(){
    cin >> n >> q;
    for(int i = 1; i <= n - 1; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    // root 1로 잡고 tree 구성
    level[1] = 1;
    dfs(1, -1);
    
    for(int j = 1; j < LOG_MAX; j++){
        for(int i = 1; i <= n; i++){
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
        }
    }
    
    for(int i = 0; i < q; i++){
        int a, b; cin >> a >> b;
        int lcaNode = lca(a, b);
        prefixSum(a, b, lcaNode);
    }
    
    pair<pair<int, int>, int> res = {{0, 0}, 0};
    
    // 결과를 오름차순으로 출력해서 이미 prefixSum으로
    // a, b / b, a section모두 구간 지나간 것을 알려줬기 때문에
    // 2중 for문 반복 횟수를 조금 줄임
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(res.second < section[i][j]){
                res = {{i, j}, section[i][j]};
            }
        }
    }
    
    cout << res.first.first << ' ' << res.first.second << ' ' << res.second;
    return 0;
}