Submission #34993

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
34993	2017-11-17T09:15:54 Z	buichitrung2001	스파이 (JOI13_spy)	C++14	0 / 100	269 ms	2680 KB

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 <60> 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;

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	2512 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	2676 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	269 ms	2680 KB	Output isn't correct
2	Halted	0 ms	0 KB	-