oj.uz

Submission #34989

# Submission time Handle Problem Language Result Execution time Memory
34989 2017-11-17T09:12:20 Z ngoduchuy64 스파이 (JOI13_spy) C++14
100 / 100
 83 ms 6376 KB 
#include <bits/stdc++.h>

using namespace std;
#define ff(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define rep(i, a, b) for(int i = (a), _b = (b); i < _b; ++i)
#define fd(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define SZ(x) ((int)(x).size())
#define db(x) cout << #x << " == " << x << endl
#define _ << ", " <<
#define X first
#define Y second
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define endl '\n'
#define pc putchar
#define gc getchar
#define bit(i) (1<<(i))
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');
       }
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;

const int N=2005;
int n,m,par_b[N];
vector<int> adj[N];
vector<int> hic[N];

void enter(){
    read(n);
    read(m);

    ff(i,1,n){
        int p,q;
        read(p);
        read(q);

        adj[p].push_back(i);

        par_b[i]=q;
    }

    ff(i,1,m){
        int r,c;
        read(r);
        read(c);
        hic[r].push_back(c);
    }
}

int cnt[N],ans[N];

void dfs(int u){

    rep(i,0,SZ(hic[u])){
        ++cnt[hic[u][i]];
    }

    for(int i=u;i;i=par_b[i]) ans[u]+=cnt[i];

    rep(i,0,SZ(adj[u])){
        int v=adj[u][i];
        dfs(v);
    }

    rep(i,0,SZ(hic[u])){
        --cnt[hic[u][i]];
    }
}

void process(){
    dfs(0);
    ff(i,1,n) writeln(ans[i]);
}

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

   // freopen("test.inp","r",stdin);
//    freopen("test.out","w",stdout);

    enter();
    process();

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2132 KB Output is correct
2 Correct 0 ms 2132 KB Output is correct
3 Correct 0 ms 2132 KB Output is correct
4 Correct 0 ms 2132 KB Output is correct
5 Correct 0 ms 2132 KB Output is correct
6 Correct 0 ms 2132 KB Output is correct
7 Correct 0 ms 2132 KB Output is correct
8 Correct 0 ms 2132 KB Output is correct
9 Correct 0 ms 2132 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2264 KB Output is correct
2 Correct 6 ms 2264 KB Output is correct
3 Correct 0 ms 2132 KB Output is correct
4 Correct 0 ms 2132 KB Output is correct
5 Correct 0 ms 2264 KB Output is correct
6 Correct 0 ms 2268 KB Output is correct
7 Correct 3 ms 2264 KB Output is correct
8 Correct 0 ms 2264 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5300 KB Output is correct
2 Correct 73 ms 6376 KB Output is correct
3 Correct 79 ms 4880 KB Output is correct
4 Correct 83 ms 6140 KB Output is correct
5 Correct 76 ms 5168 KB Output is correct
6 Correct 53 ms 6356 KB Output is correct
7 Correct 73 ms 5300 KB Output is correct
8 Correct 76 ms 5300 KB Output is correct