oj.uz

Submission #374882

# Submission time Handle Problem Language Result Execution time Memory
374882 2021-03-08T12:22:53 Z ngpin04 스파이 (JOI13_spy) C++14
100 / 100
 198 ms 8300 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 2e3 + 5;

vector <int> adj[2][N];
vector <int> todo[N];

int tin[N];
int tout[N];
int bit[N];
int ans[N];
int n,m,cntdfs,rooti, rootj;

void update(int pos, int val) {
    for (; pos <= n; pos += pos & -pos)
        bit[pos] += val;
}

void update(int l, int r, int val) {
    update(l, val);
    update(r + 1, -val);
}

int getval(int pos) {
    int res = 0;
    for (; pos; pos -= pos & -pos)
        res += bit[pos];
    return res;
}

void dfs1(int u) {
    tin[u] = ++cntdfs;
    for (int v : adj[0][u])
        dfs1(v);
    tout[u] = cntdfs;
}

void dfs2(int u) {
    for (int v : todo[u])
        update(tin[v], tout[v], 1);

    ans[u] = getval(tin[u]);

    for (int v : adj[1][u])
        dfs2(v);

    for (int v : todo[u])
        update(tin[v], tout[v], -1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int pa,pb; cin >> pa >> pb;
        if (pa == 0)
            rootj = i;
        if (pb == 0)
            rooti = i;
        adj[0][pa].push_back(i);
        adj[1][pb].push_back(i);
    }

    dfs1(rootj);

    for (int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        todo[v].push_back(u);
    }

    dfs2(rooti);

    for (int i = 1; i <= n; i++)
        cout << ans[i] << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 540 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 876 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 3 ms 688 KB Output is correct
8 Correct 2 ms 620 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 8272 KB Output is correct
2 Correct 118 ms 7364 KB Output is correct
3 Correct 118 ms 7648 KB Output is correct
4 Correct 130 ms 7776 KB Output is correct
5 Correct 125 ms 8044 KB Output is correct
6 Correct 101 ms 6728 KB Output is correct
7 Correct 156 ms 8300 KB Output is correct
8 Correct 198 ms 8172 KB Output is correct