14942 개미

14942 개미 https://www.acmicpc.net/problem/14942

개미의 집은 N개의 방으로 tree형태로 구성되어있다.
각 방에 개미 한마리씩 있고 개미마다 가진 에너지가 주어진다.
방과 방 사이를 이동할땐 일정 에너지가 소모된다.
각 방에 있는 개미가 도달할 수 있는 방 중에 1번방과 가장 가까운 방의 번호를 구하는 문제다.

각 방에서 dfs를 돌리며 답을 찾는것은 N이 $10^5$이기 때문에 시간안에 구할 수 없다.

dfs를 한번 돌려서 1번 방으로 부터 각 방에 도달하는 에너지를 sparse table형태로 구할 수 있다.

lca에서 depth를 일치시키기 위해 $2^k$만큼 변화시켜 주듯이 풀면 $O(N*logN)$만에 구할 수 있다.

#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; int N; int cost[100001]; int dist[100001][19]; int par[100001][19]; vector<pair<int, int>> adj[100001]; void solve(int here, int prev) {     for (auto &n : adj[here]) {         int next = n.second;         if (next == prev) continue;         dist[next][0] = n.first;         par[next][0] = here;         solve(next, here);     } } void init() {     for (int m = 1;m < 19;m++) {         for (int n = 1;n <= N;n++) {             par[n][m] = par[par[n][m - 1]][m - 1];             dist[n][m] = dist[par[n][m - 1]][m - 1] + dist[n][m - 1];         }     } } int main() {     scanf("%d", &N);     for (int n = 1;n <= N;n++) scanf("%d", &cost[n]);     for (int n = 0;n < N - 1;n++) {         int u, v, d;         scanf("%d%d%d", &u, &v, &d);         adj[u].push_back({ d,v });         adj[v].push_back({ d,u });     }     solve(1, -1);     init();     for (int n = 1;n <= N;n++) {         int here = n;         for (int m = 18;m >= 0;m--) {             if (cost[n] - dist[here][m] >= 0) {                 cost[n] -= dist[here][m];                 here = par[here][m];             }         }         printf("%d\n", here == 0 ? 1 : here);     }     return 0; } Colored by Color Scripter

cs