Submission #75244130

---

Source Code Expand

#line 2 "/Users/blue_jam/ProconLibrary/misc/template.hpp"

#include <atcoder/all>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

#define ALL(x) (x).begin(), (x).end()

using ll = long long;
#ifndef EPS
const double eps = 1e-10;
#else
const double eps = EPS;
#endif
#line 2 "abc455/D/main.cpp"


void solve(long long N, long long Q, std::vector<long long> C, std::vector<long long> P) {
    vector<ll> ch(N + 1, -1), pr(N + 1, -1);
    for (ll q = 0; q < Q; q++) {
        ll c = C[q], p = P[q];
        ch[p] = c;
        if (pr[c] > 0) {
            ch[pr[c]] = -1;
        }
        pr[c] = p;
    }
    for (ll i = 1; i <= N; i++) {
        ll ans;
        if (pr[i] > 0) {
            ans = 0;
        } else {
            ans = 1;
            ll p = i;
            while (ch[p] != -1) {
                ans++;
                p = ch[p];
            }
        }
        cout << ans << (i == N ? "\n" : " ");
    }
}

int main() {
    long long N;
    std::scanf("%lld", &N);
    long long Q;
    std::scanf("%lld", &Q);
    std::vector<long long> C(Q);
    std::vector<long long> P(Q);
    for(int i = 0 ; i < Q ; i++){
        std::scanf("%lld", &C[i]);
        std::scanf("%lld", &P[i]);
    }
    solve(N, Q, std::move(C), std::move(P));
    return 0;
}

Submission Info

Judge Result