oj.uz

Submission #14624

# Submission time Handle Problem Language Result Execution time Memory
14624 2015-05-22T15:17:06 Z dohyun0324 Synchronization (JOI13_synchronization) C++
50 / 100
 1808 ms 26032 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[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[1000],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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18432 KB Output is correct
2 Correct 0 ms 18432 KB Output is correct
3 Correct 4 ms 18432 KB Output is correct
4 Correct 0 ms 18432 KB Output is correct
5 Correct 4 ms 18432 KB Output is correct
6 Correct 15 ms 18432 KB Output is correct
7 Correct 74 ms 18696 KB Output is correct
8 Correct 76 ms 18696 KB Output is correct
9 Correct 79 ms 18696 KB Output is correct
10 Correct 1457 ms 22128 KB Output is correct
11 Correct 1468 ms 22128 KB Output is correct
12 Correct 1007 ms 26028 KB Output is correct
13 Incorrect 1808 ms 22496 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 864 ms 24224 KB Output is correct
2 Correct 843 ms 24164 KB Output is correct
3 Correct 534 ms 26032 KB Output is correct
4 Correct 547 ms 26024 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18432 KB Output is correct
2 Correct 0 ms 18432 KB Output is correct
3 Correct 3 ms 18432 KB Output is correct
4 Correct 3 ms 18432 KB Output is correct
5 Correct 5 ms 18432 KB Output is correct
6 Correct 15 ms 18432 KB Output is correct
7 Correct 71 ms 19040 KB Output is correct
8 Correct 1055 ms 26028 KB Output is correct
9 Correct 1049 ms 26032 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 26032 KB Output is correct
2 Correct 593 ms 25996 KB Output is correct
3 Correct 564 ms 26032 KB Output is correct
4 Correct 564 ms 26032 KB Output is correct

Subtask #5
0.0 / 40.0

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