oj.uz

Submission #34963

# Submission time Handle Problem Language Result Execution time Memory
34963 2017-11-17T08:55:55 Z littlecutebird 스파이 (JOI13_spy) C++14
100 / 100
 366 ms 247840 KB 
#include <bits/stdc++.h>
#define long long long
#define up(i,a,b) for (int i=a; i<=b; i++)
#define down(i,a,b) for (int i=a; i>=b; i--)
#define endl '\n'
#define X first
#define Y second
#define II pair<int, int>
#define III pair<int, pair<int, int> >
#define debug(X) cerr<< #X << "=" <<X << endl
#define debug2(X,Y) cerr<< #X << "=" <<X << " , "<< #Y << "=" <<Y << endl
#define show(X,a,b) {cerr << #X << " = "; up(__,a,b) cerr << X[__] << ' '; cerr << endl;}
#define gc getchar
#define pc putchar
using namespace std;

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');
       }
const int N= 2010;
const int M= 5e5+10;
int n,m,ra,rb;
vector<int> a[N],b[N];
bitset<M> da[N],db[N],steal;
void input()
{
    read(n); read(m);
    up(i,1,n )
    {
        int p,q; read(p); read(q);
        if (p!= 0)
        {
            a[p].push_back(i);
        }
        else ra= i;
        if (q!= 0)
        {
            b[q].push_back(i);
        }
        else rb= i;
    }
    up(i,1,m)
    {
        int r,s; read(r); read(s);
        da[r].set(i);
        db[s].set(i);
    }
}

void dfs_a(int r,int p)
{
    if (p!= 0) da[r]|= da[p];
    for (auto u: a[r]) dfs_a(u,r);
}
void dfs_b(int r,int p)
{
    if (p!= 0) db[r]|= db[p];
    for (auto u: b[r]) dfs_b(u,r);
}
void solve()
{
    dfs_a(ra,0);
    dfs_b(rb,0);
    up(i,1,n)
    {
        steal= da[i]& db[i];
       writeln(steal.count() );
    };
}

int main()
{
    ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    #ifdef I_Love_Pork
    #define TASK "tmp"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
    #endif

    input();
    solve();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 247708 KB Output is correct
2 Correct 16 ms 247708 KB Output is correct
3 Correct 19 ms 247708 KB Output is correct
4 Correct 13 ms 247708 KB Output is correct
5 Correct 19 ms 247708 KB Output is correct
6 Correct 13 ms 247708 KB Output is correct
7 Correct 9 ms 247708 KB Output is correct
8 Correct 23 ms 247708 KB Output is correct
9 Correct 0 ms 247708 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 247840 KB Output is correct
2 Correct 179 ms 247840 KB Output is correct
3 Correct 163 ms 247708 KB Output is correct
4 Correct 156 ms 247708 KB Output is correct
5 Correct 173 ms 247708 KB Output is correct
6 Correct 176 ms 247708 KB Output is correct
7 Correct 186 ms 247840 KB Output is correct
8 Correct 169 ms 247840 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 247840 KB Output is correct
2 Correct 199 ms 247840 KB Output is correct
3 Correct 303 ms 247708 KB Output is correct
4 Correct 273 ms 247708 KB Output is correct
5 Correct 366 ms 247708 KB Output is correct
6 Correct 226 ms 247708 KB Output is correct
7 Correct 359 ms 247840 KB Output is correct
8 Correct 343 ms 247840 KB Output is correct