oj.uz

답안 #13714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13714 2015-03-28T14:39:14 Z gs14004 스파이 (JOI13_spy) C++14
0 / 100
 2000 ms 1352 KB 
#include <cstdio>
#include <vector>
using namespace std;

int n,m;
int rj,ri;

vector<int> jg[2005], ig[2005];

int jdf[2005], idf[2005], jsz[2005], isz[2005], jrv[2005], irv[2005];
int jp, ip;

int jdfs(int x){
    jdf[x] = ++jp;
    jrv[jp] = x;
    int ret = 1;
    for (auto &i : jg[x]){
        ret += jdfs(i);
    }
    return jsz[x] = ret;
}

int idfs(int x){
    idf[x] = ++ip;
    irv[ip] = x;
    int ret = 1;
    for (auto &i : ig[x]){
        ret += idfs(i);
    }
    return isz[x] = ret;
}

int main(){
    scanf("%d %d",&n,&m);
    for (int i=1; i<=n; i++) {
        int p,q;
        scanf("%d %d",&p,&q);
        if(p == 0) rj = i;
        else jg[p].push_back(i);
        if(q == 0) ri = i;
        else ig[q].push_back(i);
    }
    jdfs(rj);
    idfs(ri);
    int cnt[2005] = {};
    while (m--) {
        int lj, li;
        scanf("%d %d",&lj,&li);
        for (int i=idf[li]; i<idf[li] + isz[li]; i++) {
            int rev = irv[i];
            if(jdf[lj] <= rev && rev < jdf[lj] + jsz[lj]){
                cnt[rev]++;
            }
        }
    }
    for (int i=1; i<=n; i++) {
        printf("%d\n",cnt[i]);
    }
}

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 1352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 1352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 1352 KB Program timed out
2 Halted 0 ms 0 KB -