oj.uz

Submission #958393

# Submission time Handle Problem Language Result Execution time Memory
958393 2024-04-05T18:00:55 Z gmroh06 스파이 (JOI13_spy) C++17
100 / 100
 76 ms 11964 KB 
#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;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 452 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 604 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 11344 KB Output is correct
2 Correct 63 ms 11964 KB Output is correct
3 Correct 76 ms 10176 KB Output is correct
4 Correct 60 ms 10820 KB Output is correct
5 Correct 61 ms 11060 KB Output is correct
6 Correct 55 ms 10684 KB Output is correct
7 Correct 64 ms 11312 KB Output is correct
8 Correct 69 ms 11348 KB Output is correct