oj.uz

Submission #14626

# Submission time Handle Problem Language Result Execution time Memory
14626 2015-05-22T15:20:20 Z dohyun0324 Synchronization (JOI13_synchronization) C++
50 / 100
 1921 ms 38540 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;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);
    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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 4 ms 30940 KB Output is correct
5 Correct 4 ms 30940 KB Output is correct
6 Correct 16 ms 30940 KB Output is correct
7 Correct 87 ms 31204 KB Output is correct
8 Correct 99 ms 31204 KB Output is correct
9 Correct 98 ms 31204 KB Output is correct
10 Correct 1554 ms 34636 KB Output is correct
11 Correct 1534 ms 34636 KB Output is correct
12 Correct 1082 ms 38540 KB Output is correct
13 Incorrect 1921 ms 35004 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 952 ms 36736 KB Output is correct
2 Correct 940 ms 36676 KB Output is correct
3 Correct 586 ms 38540 KB Output is correct
4 Correct 592 ms 38540 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 8 ms 30940 KB Output is correct
3 Correct 10 ms 30940 KB Output is correct
4 Correct 6 ms 30940 KB Output is correct
5 Correct 5 ms 30940 KB Output is correct
6 Correct 20 ms 30940 KB Output is correct
7 Correct 86 ms 31548 KB Output is correct
8 Correct 1090 ms 38540 KB Output is correct
9 Correct 1108 ms 38536 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 38536 KB Output is correct
2 Correct 645 ms 38508 KB Output is correct
3 Correct 645 ms 38540 KB Output is correct
4 Correct 627 ms 38536 KB Output is correct

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 12 ms 30940 KB Output is correct
5 Incorrect 18 ms 30940 KB Output isn't correct
6 Halted 0 ms 0 KB -