Submission #35036

#	Time	Username	Problem	Language	Result	Execution time	Memory
35036		buichitrung2001	스파이 (JOI13_spy)	C++14	100 / 100	379 ms	9852 KiB

spy

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <bitset>
#define Tpair pair <int, int>
#define gc getchar
#define pc putchar
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 <5000> sum[3][2005], bit[3], res[3][2005];
vector <int> v[3][2005];

inline void read(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for (;((c<48 || c>57) && c != '-') ;c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}

inline void writeln(int x){

         char buffor[21];
         register int i=0;
         int neg=0; if (x<0) {neg=1; x= -x;}
         do{
               buffor[i++]=(x%10)+'0';
               x/=10;
            } while(x);
           i--;
           if (neg) pc('-');
           while(i>=0) pc(buffor[i--]);
           pc('\n');
       }

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;
    read(n); read(m);
    for (int i = 1; i <= n; ++i)
    {
        //cin >> p[1] >> p[2];
        read(p[1]); read(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];
        read(s[1]); read(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;

        if (dem == 5000) Reset();
        ++dem;
    }
    Reset();
    for (int i = 1; i <= n; ++i) writeln(ans[i]);
}

int main()
{
    //freopen ("spy.inp", "r", stdin);
    //freopen ("spy.out", "w", stdout);

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

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