結果

問題 No.3405 Engineering University of Tree
コンテスト
ユーザー The Forsaking
提出日時 2025-12-16 22:59:59
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 635 ms / 2,000 ms
コード長 1,582 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,114 ms
コンパイル使用メモリ 205,260 KB
実行使用メモリ 57,000 KB
最終ジャッジ日時 2025-12-16 23:00:12
合計ジャッジ時間 13,109 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:44:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   44 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:48:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   48 |         scanf("%d", &c);
      |         ~~~~~^~~~~~~~~~
main.cpp:50:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |             scanf("%d", &a);
      |             ~~~~~^~~~~~~~~~

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000010, MOD = 998244353, INF = 0x3f3f3f3f;
int n, m, w[N];


int e[N], ne[N], h[N], idx, p[N], d[N];
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void dfs(int r) {
    for (int i = h[r]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == p[r]) continue;
        p[j] = r, d[j] = d[r] - 1;
        dfs(j);
    }
}

int sum, v[N];
bool f[N];
set<pii> st[200010];

void ch(int x, int t, int g) {
    sum -= v[x] >= t;
    st[v[x]].erase({d[x], x});

    v[x] += g;
    if (v[x] != t && f[x]) {
        f[x] = 0, v[x]--;
        ch(p[x], t, 1);
    } else if (v[x] == t - 1 && !f[x] && p[x]) {
        f[x] = 1, v[x]++;
        ch(p[x], t, -1);
    }

    st[v[x]].insert({d[x], x});
    sum += v[x] >= t;
}

int main() {
    scanf("%d", &n);
    vector<int> b(n);
    memset(h, -1, sizeof h);
    for (int i = 1, c, a; i < n + 1; i++) {
        scanf("%d", &c);
        while (c--) {
            scanf("%d", &a);
            if (b[a]) add(i, b[a]), add(b[a], i);
            else b[a] = i;
        }
    }
    dfs(1);
    sum = n - 1;
    st[0].insert({0, 1});
    for (int i = 2; i < n + 1; i++) st[1].insert({d[i], i}), v[i] = f[i] = 1;
    printf("%d ", sum);
    for (int i = 2; i < n; i++) {
        sum -= st[i - 1].size();
        vector<int> t;
        for (auto u : st[i - 1]) t.push_back(u.second);
        for (auto u : t)
            if (v[u] == i - 1)
                ch(u, i, 0);
        printf("%d ", sum);
    }
    return 0;
}
0