글 읽기 - 진짜 모르겠다 help me

qkrwndnjs 3년 전 0

정답이 나올때도 있고 안나올때도 있고(죽는다고 해야하나? 제출하면 런타임 에러라고 나옴) 왔다갔다 이런적은 처음인데...

진짜 모르겠슴돠 help me

#include <bits/stdc++.h>
using namespace std;
vector <pair<int, int>> tree_sg, num_sg;
vector <int> idx_sg;
vector <vector<int>> tree;
void makeidx_sg(int depth, int now, int before) {
    num_sg.push_back(make_pair(depth, now));
    idx_sg[now] = num_sg.size() - 1;
    for (int i = 0; i < tree[now].size(); i++) {
        if (tree[now][i] == before) continue;
        makeidx_sg(depth + 1, tree[now][i], now);
        num_sg.push_back(make_pair(depth, now));
    }
}
pair <int, int> init_sg(int left, int right, int node) {
    if (left == right) return tree_sg[node] = num_sg[left];
    int mid = (left + right) / 2;
    return tree_sg[node] = min(init_sg(left, mid, node * 2 + 1), init_sg(mid + 1, right, node * 2 + 2));
}
pair <int, int> Find(int left, int right, int s, int e, int node) {
    if (right < s || e < left) return make_pair(1e9, 1e9);
    if (s <= left && right <= e) return tree_sg[node];
    int mid = (left + right) / 2;
    return min(Find(left, mid, s, e, node * 2 + 1), Find(mid + 1, right, s, e, node * 2 + 2));
}
int main(void)
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n, m; cin >> n; tree.resize(n), tree_sg.resize(n * 4), idx_sg.resize(n);
    for (int a, b, i = 0; i < n - 1; i++) {
        cin >> a >> b;
        tree[--a].push_back(--b), tree[b].push_back(a);
    }
    makeidx_sg(0, 0, -1); init_sg(0, num_sg.size() - 1, 0);
    cin >> m;
    for (int a, b, i = 0; i < m; i++) {
        cin >> a >> b;
        cout << Find(0, num_sg.size() - 1, min(idx_sg[a - 1], idx_sg[b - 1]), max(idx_sg[a - 1], idx_sg[b - 1]), 0).second + 1 << '\n';
    }
    return 0;
}

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

문제

문제

출처

ICPC

진짜 모르겠다 help me

qkrwndnjs 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말