제출 #958393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
958393		gmroh06	스파이 (JOI13_spy)	C++17	100 / 100	76 ms	11964 KiB

spy

#import <bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

inline void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

ll n, m, root;
vector<ll> p, q, ans, cnt;
vector<vector<ll>> gr, pr;

inline void init() {
    p.resize(n);
    q.resize(n);
    gr.resize(n);
    pr.resize(n);
    cnt.resize(n);
    ans.resize(n);
}

ll count(ll idx) {
    ll ret = 0;

    while (idx + 1) {
        ret += cnt[idx];
        idx = q[idx];
    }

    return ret;
}

void dfs(const ll& loc) {
    for (const auto& x : pr[loc]) {
        cnt[x]++;
    }

    ans[loc] = count(loc);

    for (const auto& x : gr[loc]) {
        dfs(x);
    }

    for (const auto& x : pr[loc]) {
        cnt[x]--;
    }
}

int main() {
    fastio();

    cin >> n >> m;

    init();

    for (ll i = 0; i < n; i++) {
        auto a = p.begin() + i, b = q.begin() + i;

        cin >> *a >> *b;
        (*a)--, (*b)--;

        if (*a == -1) {
            root = i;
        } else {
            gr[*a].emplace_back(i);
        }
    }

    for (ll i = 0, r, s; i < m; i++) {
        cin >> r >> s;

        pr[r - 1].emplace_back(s - 1);
    }

    dfs(root);

    for (const auto& x : ans) {
        cout << x << ' ';
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

spy.cpp:1:2: warning: #import is a deprecated GCC extension [-Wdeprecated]
    1 | #import <bits/stdc++.h>
      |  ^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70