oj.uz

Submission #14627

# Submission time Handle Problem Language Result Execution time Memory
14627 2015-05-22T15:29:39 Z dohyun0324 Synchronization (JOI13_synchronization) C++
100 / 100
 1976 ms 38544 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
typedef pair<int,int> ppair;
vector<ppair>con[400010];
int ch3[400010],val2,dap[400010],pos[400010],w2,en[400010],counter[400010],val,cnt,p[400010],num[400010],t,n,m,q,c,w,arr[1000],save[400010],arr2[2000],group[400010],ch[400010],ch2[400010];
struct data{
    int x,y;
}e[400010];
void dfs2(int x)
{
    int i;
    ch2[x]=1; group[x]=val; dap[x]=val2;
    for(i=0;i<con[x].size();i++){
        if(ch[con[x][i].second]==1 && ch2[con[x][i].first]==0) dfs2(con[x][i].first);
    }
}
void pro()
{
    memset(ch3,0,sizeof ch3);
    int i,j,s1,e1,x1,x2,k=0,p1,p2;
    for(i=1;i<=w;i++)
    {
        ch[arr[i]]=!ch[arr[i]]; x1=group[p[arr[i]*2]]; x2=group[p[arr[i]*2+1]]; p1=dap[p[arr[i]*2+1]]; p2=dap[p[arr[i]*2]];
        s1=num[p[arr[i]*2]]; e1=en[p[arr[i]*2]];
        if(ch[arr[i]]==0) cnt++;
        for(j=1;j<=w2;j++)
        {
            if(s1<=num[arr2[j]] && num[arr2[j]]<=e1 && group[arr2[j]]==x1)
            {
                if(ch[arr[i]]) group[arr2[j]]=x2, dap[arr2[j]]+=(p1-save[arr[i]*2+1]);
                else group[arr2[j]]=cnt, save[arr[i]*2]=dap[arr2[j]];
            }
            if(!(s1<=num[arr2[j]] && num[arr2[j]]<=e1) && group[arr2[j]]==x2)
            {
                if(ch[arr[i]]) dap[arr2[j]]+=(p2-save[arr[i]*2]);
                else save[arr[i]*2+1]=dap[arr2[j]];
            }
        }
    }
    memset(ch2,0,sizeof ch2); memset(counter,0,sizeof counter);
    for(i=1;i<=w2;i++){
        val=group[arr2[i]]; val2=dap[arr2[i]];
        if(ch2[arr2[i]]==0) dfs2(arr2[i]);
    }
    for(i=1;i<=n;i++) counter[group[i]]=1;
    for(i=1;i<=n+w;i++) if(counter[i]) pos[i]=++k;
    cnt=k;
    for(i=1;i<=n;i++) group[i]=pos[group[i]];
}
void dfs(int x)
{
    int i;
    num[x]=++t; ch2[x]=1;
    for(i=0;i<con[x].size();i++){
        if(ch2[con[x][i].first]) continue;
        p[con[x][i].second*2]=con[x][i].first;
        p[con[x][i].second*2+1]=x;
        dfs(con[x][i].first);
    }
    en[x]=t;
}
int main()
{
    int i,x;
    scanf("%d %d %d",&n,&m,&q);
    for(i=1;i<=n;i++) group[i]=i, dap[i]=1;
    for(i=1;i<=n-1;i++){
        scanf("%d %d",&e[i].x,&e[i].y);
        con[e[i].x].push_back(make_pair(e[i].y,i));
        con[e[i].y].push_back(make_pair(e[i].x,i));
    }
    dfs(1);
    c=sqrt(m); cnt=n;
    for(i=1;i<=m;i++){
        scanf("%d",&arr[++w]);
        if(ch3[e[arr[w]].x]==0) arr2[++w2]=e[arr[w]].x, ch3[e[arr[w]].x]=1;
        if(ch3[e[arr[w]].y]==0) arr2[++w2]=e[arr[w]].y, ch3[e[arr[w]].y]=1;
        if(i%c==0 || i==m) pro(), w=0, w2=0;
    }
    for(i=1;i<=q;i++){
        scanf("%d",&x);
        printf("%d\n",dap[x]);
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30940 KB Output is correct
2 Correct 3 ms 30940 KB Output is correct
3 Correct 4 ms 30940 KB Output is correct
4 Correct 4 ms 30940 KB Output is correct
5 Correct 11 ms 30940 KB Output is correct
6 Correct 20 ms 30940 KB Output is correct
7 Correct 92 ms 31204 KB Output is correct
8 Correct 95 ms 31204 KB Output is correct
9 Correct 94 ms 31204 KB Output is correct
10 Correct 1580 ms 34636 KB Output is correct
11 Correct 1573 ms 34636 KB Output is correct
12 Correct 1090 ms 38536 KB Output is correct
13 Correct 1948 ms 35004 KB Output is correct
14 Correct 1089 ms 34636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 36732 KB Output is correct
2 Correct 952 ms 36672 KB Output is correct
3 Correct 603 ms 38544 KB Output is correct
4 Correct 603 ms 38536 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30940 KB Output is correct
2 Correct 4 ms 30940 KB Output is correct
3 Correct 4 ms 30940 KB Output is correct
4 Correct 8 ms 30940 KB Output is correct
5 Correct 7 ms 30940 KB Output is correct
6 Correct 20 ms 30940 KB Output is correct
7 Correct 79 ms 31548 KB Output is correct
8 Correct 1124 ms 38540 KB Output is correct
9 Correct 1114 ms 38536 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1091 ms 38540 KB Output is correct
2 Correct 637 ms 38504 KB Output is correct
3 Correct 612 ms 38540 KB Output is correct
4 Correct 630 ms 38536 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30940 KB Output is correct
2 Correct 0 ms 30940 KB Output is correct
3 Correct 4 ms 30940 KB Output is correct
4 Correct 9 ms 30940 KB Output is correct
5 Correct 16 ms 30940 KB Output is correct
6 Correct 95 ms 31204 KB Output is correct
7 Correct 1585 ms 34636 KB Output is correct
8 Correct 1116 ms 38540 KB Output is correct
9 Correct 1976 ms 35004 KB Output is correct
10 Correct 1162 ms 34636 KB Output is correct
11 Correct 982 ms 36740 KB Output is correct
12 Correct 1012 ms 36736 KB Output is correct
13 Correct 616 ms 38536 KB Output is correct