oj.uz

Submission #34961

# Submission time Handle Problem Language Result Execution time Memory
34961 2017-11-17T08:54:15 Z littlecutebird 스파이 (JOI13_spy) C++14
10 / 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()
{
    cin>>n>>m;
    up(i,1,n )
    {
        int p,q; cin>>p>>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; cin>>r>>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];
        cout<<steal.count() <<endl;
    };
}

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

    input();
    solve();

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 247840 KB Output is correct
2 Runtime error 143 ms 247840 KB Execution killed because of forbidden syscall writev (20)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 366 ms 247840 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -