Submission #12962

#	Time	Username	Problem	Language	Result	Execution time	Memory
12962		dohyun0324	스파이 (JOI13_spy)	C++98	100 / 100	200 ms	48480 KiB

spy

#include<stdio.h>
int n,m,con1[2010][2010],w1[2010];
int cnt,con2[2010][2010],w2[2010],num1[2010],num2[2010],en1[2010],en2[2010];
int d[2010][2010];
void dfs1(int x)
{
    int i;
    num1[x]=++cnt;
    for(i=1;i<=w1[x];i++) dfs1(con1[x][i]);
    en1[x]=cnt;
}
void dfs2(int x)
{
    int i;
    num2[x]=++cnt;
    for(i=1;i<=w2[x];i++) dfs2(con2[x][i]);
    en2[x]=cnt;
}
void update(int x1,int x2,int y1,int y2){
    d[x1][y1]++; d[x1][y2+1]--;
    d[x2+1][y1]--; d[x2+1][y2+1]++;
}
int main()
{
    int i,j,x,y,s1,s2;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d %d",&x,&y);
        if(x!=0) con1[x][++w1[x]]=i;
        else s1=i;
        if(y!=0) con2[y][++w2[y]]=i;
        else s2=i;
    }
    dfs1(s1); cnt=0; dfs2(s2);
    for(i=1;i<=m;i++){
        scanf("%d %d",&x,&y);
        update(num1[x],en1[x],num2[y],en2[y]);
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            d[i][j]+=d[i][j-1];
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            d[i][j]+=d[i-1][j];
        }
    }
    for(i=1;i<=n;i++) printf("%d\n",d[num1[i]][num2[i]]);
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70