Submission #34978

#	Time	Username	Problem	Language	Result	Execution time	Memory
34978		buichitrung2001	스파이 (JOI13_spy)	C++14	0 / 100	336 ms	2680 KiB

spy

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <bitset>
#define Tpair pair <int, int>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 5;
const int mod  = 1e9 + 7;
const int oo   = 1e9 + 1;

int n, m, i, T, par[3][2005], child[3][2005], pos[3][2005], cnt[3], p[3], root[3], s[3],
ans[2005], pos2[3][2005], dem;
bitset <60> sum[3][2005], bit[3], res[3][2005];
vector <int> v[3][2005];

void Dfs (int x, int pre, int idx)
{
    par[idx][x] = pre;
    child[idx][x] = 1;
    pos[idx][x] = ++cnt[idx];
    pos2[idx][cnt[idx]] = x;
    for (int j : v[idx][x])
        if (!par[idx][j])
        {
            Dfs (j, x, idx);
            child[idx][x] += child[idx][j];
        }
}

void Init()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> p[1] >> p[2];
        if (p[1] != 0) v[1][p[1]].push_back (i);
        if (p[2] != 0) v[2][p[2]].push_back (i);
        if (p[1] == 0) root[1] = i;
        if (p[2] == 0) root[2] = i;
    }

    Dfs (root[1], root[1], 1);
    Dfs (root[2], root[2], 2);

    //for (int i = 1; i <= n; ++i) cout << i << " " << par[1][i] << " " << child[1][i] << " " << pos[1][i] << '\n';
    //for (int i = 1; i <= n; ++i) cout << i << " " << par[2][i] << " " << child[2][i] << " " << pos[2][i] << '\n';
}

void Reset()
{
    for (int i = 1; i <= n; ++i)
    {
        bit[1] ^= sum[1][i];
        bit[2] ^= sum[2][i];
        res[1][i] = bit[1];
        res[2][i] = bit[2];
        //cout << sum[1][i] << endl << sum[2][i] << endl;
    }
    for (int i = 1; i <= n; ++i) ans[i] = (res[1][pos[1][i]] & res[2][pos[2][i]]).count();

    dem = 0;
    for (int i = 1; i <= n; ++i)
    {
        res[1][i].reset();
        res[2][i].reset();
        sum[1][i].reset();
        sum[2][i].reset();
    }
    bit[1].reset(); bit[2].reset();
}

void Solve()
{
    for (int i = 1; i <= m; ++i)
    {
        cin >> s[1] >> s[2];
        sum[1][pos[1][s[1]]][dem] = 1;
        sum[2][pos[2][s[2]]][dem] = 1;
        sum[1][pos[1][s[1]] + child[1][s[1]]][dem] = 1;
        sum[2][pos[2][s[2]] + child[2][s[2]]][dem] = 1;

        ++dem;
        if (i % 60 == 0) Reset();
    }
    Reset();
    for (int i = 1; i <= n; ++i) cout << ans[i] << '\n';
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen ("spy.inp", "r", stdin);
    //freopen ("spy.out", "w", stdout);

    Init();
    Solve();
}
// Date 15 Month 11 Year 2017

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