oj.uz

Submission #12962

# Submission time Handle Problem Language Result Execution time Memory
12962 2015-01-21T16:44:49 Z dohyun0324 스파이 (JOI13_spy) C++
100 / 100
 200 ms 48480 KB 
#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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 48480 KB Output is correct
2 Correct 16 ms 48480 KB Output is correct
3 Correct 24 ms 48480 KB Output is correct
4 Correct 16 ms 48480 KB Output is correct
5 Correct 16 ms 48480 KB Output is correct
6 Correct 24 ms 48480 KB Output is correct
7 Correct 16 ms 48480 KB Output is correct
8 Correct 24 ms 48480 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 48480 KB Output is correct
2 Correct 128 ms 48480 KB Output is correct
3 Correct 152 ms 48480 KB Output is correct
4 Correct 156 ms 48480 KB Output is correct
5 Correct 168 ms 48480 KB Output is correct
6 Correct 128 ms 48480 KB Output is correct
7 Correct 188 ms 48480 KB Output is correct
8 Correct 200 ms 48480 KB Output is correct