Submission #1244506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244506		tvgk	스파이 (JOI13_spy)	C++20	100 / 100	165 ms	129508 KiB

spy

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e3 + 7, mxX = 5e5 + 2;

bitset<mxX> mut, ans[mxN];
vector<int> querry[mxN][2], w[mxN][2];
int n, q, root[2];

void DFS(int j, bool id)
{
    for (int i : querry[j][id])
        mut.set(i - 1);

    if (!id)
        ans[j] = mut;
    else
        ans[j] &= mut;

    for (int i : w[j][id])
        DFS(i, id);

    for (int i : querry[j][id])
        mut.reset(i - 1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        for (int u = 0; u <= 1; u++)
        {
            int par;
            cin >> par;
            w[par][u].push_back(i);
        }
    }

    for (int i = 1; i <= q; i++)
    {
        for (int u = 0; u <= 1; u++)
        {
            int par;
            cin >> par;
            querry[par][u].push_back(i);

            if (!par)
                root[u] = i;
        }
    }
    DFS(root[0], 0);
    DFS(root[1], 1);

    for (int i = 1; i <= n; i++)
        cout << ans[i].count() << '\n';
}

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