oj.uz

Submission #14625

# Submission time Handle Problem Language Result Execution time Memory
14625 2015-05-22T15:19:49 Z dohyun0324 Synchronization (JOI13_synchronization) C++
50 / 100
 1878 ms 38532 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[500],save[400010],arr2[1000],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 3 ms 30932 KB Output is correct
2 Correct 8 ms 30932 KB Output is correct
3 Correct 4 ms 30932 KB Output is correct
4 Correct 2 ms 30932 KB Output is correct
5 Correct 7 ms 30932 KB Output is correct
6 Correct 17 ms 30932 KB Output is correct
7 Correct 93 ms 31196 KB Output is correct
8 Correct 91 ms 31196 KB Output is correct
9 Correct 85 ms 31196 KB Output is correct
10 Correct 1500 ms 34628 KB Output is correct
11 Correct 1535 ms 34628 KB Output is correct
12 Correct 1081 ms 38532 KB Output is correct
13 Incorrect 1878 ms 34996 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 942 ms 36728 KB Output is correct
2 Correct 917 ms 36672 KB Output is correct
3 Correct 591 ms 38528 KB Output is correct
4 Correct 613 ms 38528 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 30932 KB Output is correct
2 Correct 8 ms 30932 KB Output is correct
3 Correct 11 ms 30932 KB Output is correct
4 Correct 10 ms 30932 KB Output is correct
5 Correct 5 ms 30932 KB Output is correct
6 Correct 22 ms 30932 KB Output is correct
7 Correct 85 ms 31536 KB Output is correct
8 Correct 1100 ms 38528 KB Output is correct
9 Correct 1096 ms 38528 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1097 ms 38532 KB Output is correct
2 Correct 622 ms 38496 KB Output is correct
3 Correct 638 ms 38528 KB Output is correct
4 Correct 632 ms 38532 KB Output is correct

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 30932 KB Output is correct
2 Correct 4 ms 30932 KB Output is correct
3 Correct 0 ms 30932 KB Output is correct
4 Correct 8 ms 30932 KB Output is correct
5 Incorrect 20 ms 30932 KB Output isn't correct
6 Halted 0 ms 0 KB -