Submission #14623

#	Time	Username	Problem	Language	Result	Execution time	Memory
14623		dohyun0324	Synchronization (JOI13_synchronization)	C++98	20 / 100	861 ms	26028 KiB

synchronization

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
typedef pair<int,int> ppair;
vector<ppair>con[200010];
int ch3[200010],val2,dap[200010],pos[200010],w2,en[200010],counter[400010],val,cnt,p[400010],num[200010],t,n,m,q,c,w,arr[500],save[400010],arr2[500],group[200010],ch[200010],ch2[200010];
struct data{
    int x,y;
}e[200010];
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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40