Submission #13714

#	Time	Username	Problem	Language	Result	Execution time	Memory
13714		gs14004	스파이 (JOI13_spy)	C++14	0 / 100	2000 ms	1352 KiB

spy

#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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70