Submission #374882

#	Time	Username	Problem	Language	Result	Execution time	Memory
374882		ngpin04	스파이 (JOI13_spy)	C++14	100 / 100	198 ms	8300 KiB

spy

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70