結果

問題 No.3189 Semifinal Stage
コンテスト
ユーザー Mitarushi
提出日時 2025-06-15 17:57:07
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 670 ms / 4,000 ms
コード長 2,458 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,015 ms
コンパイル使用メモリ 84,816 KB
実行使用メモリ 59,348 KB
最終ジャッジ日時 2025-06-19 19:14:26
合計ジャッジ時間 15,407 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:64:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   64 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:71:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   71 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:82:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   82 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
main.cpp:85:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   85 |         scanf("%d %d", &t, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <vector>
#include <utility>
#include <set>

int n;
std::vector<std::vector<int>> graph;
std::vector<char> cut_mark;

int get_size(int v, int p) {
    int s = 1;
    for (int u : graph[v]) {
        if (u == p || cut_mark[u]) {
            continue;
        }
        s += get_size(u, v);
    }
    return s;
}

std::pair<int, int> find_centroid(int v, int p, int total) {
    int s = 1;
    for (int u : graph[v]) {
        if (u == p || cut_mark[u]) {
            continue;
        }
        auto [cs, c] = find_centroid(u, v, total);
        if (c != -1) {
            return {0, c};
        }
        s += cs;
    }
    if (total - s <= total / 2) {
        return {0, v};
    }
    return {s, -1};
}

std::vector<std::vector<std::pair<int, int>>> c_dist;
void set_dist(int v, int p, int c, int d) {
    c_dist[v].emplace_back(c, d);
    for (int u : graph[v]) {
        if (u == p || cut_mark[u]) {
            continue;
        }
        set_dist(u, v, c, d + 1);
    }
}

void decompose(int v) {
    int total = get_size(v, -1);
    auto [_, c] = find_centroid(v, -1, total);
    cut_mark[c] = true;
    set_dist(c, -1, c, 0);
    for (int u : graph[c]) {
        if (cut_mark[u]) {
            continue;
        }
        decompose(u);
    }
}

int main() {
    scanf("%d", &n);
    graph.resize(n);
    cut_mark.resize(n, false);
    c_dist.resize(n);

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        --u; --v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    decompose(0);

    std::vector<std::multiset<int>> black_pq(n);
    std::vector<int> color(n, 0);
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; ++i) {
        int t, v;
        scanf("%d %d", &t, &v);
        --v;

        if (t == 1) {
            if (color[v] == 0) {
                for (const auto& [c, d] : c_dist[v]) {
                    black_pq[c].insert(d);
                }
            } else {
                for (const auto& [c, d] : c_dist[v]) {
                    black_pq[c].erase(black_pq[c].find(d));
                }
            }
            color[v] = 1 - color[v];
        } else {
            int ans = n;
            for (const auto& [c, d] : c_dist[v]) {
                if (!black_pq[c].empty()) {
                    ans = std::min(ans, d + *black_pq[c].begin());
                }
            }
            printf("%d\n", ans);
        }
    }
}
0