oj.uz

Submission #936974

# Submission time Handle Problem Language Result Execution time Memory
936974 2024-03-03T07:20:53 Z sleepntsheep Synchronization (JOI13_synchronization) C
100 / 100
 205 ms 15840 KB 
#include<stdio.h>
#include<stdlib.h>
#define N 100009
int n,m,q,on[N],e[N][2],*eh[N],eo[N],tin[N],tout[N],timer,a[N],c[N],pp[N],jj[N],dd[N],ac[N];
void upd(int*t,int p,int k){ for(;p<N;p|=p+1)t[p]+=k; }
int qry(int*t,int p){++p;int z=0;for(;p;p&=p-1)z+=t[p-1];return z;}
void append(int i,int k){
    int o=eo[i]++;
    if(o >= 2 && !(o & (o-1))) eh[i] = (int*)realloc(eh[i], o*2*sizeof**eh);
    eh[i][o]=k;
}
void dfs(int u,int p){
    dd[u]=dd[pp[u]=p]+1;
    if(dd[p]-dd[jj[p]]==dd[jj[p]]-dd[jj[jj[p]]])jj[u]=jj[jj[p]];else jj[u]=p;
    tin[u]=timer++;
    for(int j=0;j<eo[u];++j)if(eh[u][j]-p)dfs(eh[u][j],u);
    tout[u]=timer-1;
}
int findroot(int u){
    while(u!=1&&qry(ac,tin[u])-qry(ac,tin[pp[u]])==1)
        u=(qry(ac,tin[u])-qry(ac,tin[jj[u]])==dd[u]-dd[jj[u]])?jj[u]:pp[u];
    return u;
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i)eh[i]=(int*)malloc(2*sizeof**eh),a[i]=1;
    for(int i=1;i<n;++i)scanf("%d%d",e[i],e[i]+1),append(e[i][0],e[i][1]),append(e[i][1],e[i][0]);
    pp[1]=jj[1]=1;dfs(1,1);
    for(int tt,r,u,v,ii,i=0;i<m;++i){
        scanf("%d",&ii);u=e[ii][0],v=e[ii][1];
        if(dd[v]<dd[u])tt=u,u=v,v=tt;
        r=findroot(u);
        if(on[ii]^=1){
            upd(ac,tin[v],1),upd(ac,tout[v]+1,-1);
            a[r]=a[r]-c[v]+a[v];
        }else{
            upd(ac,tin[v],-1),upd(ac,tout[v]+1,1);
            c[v]=a[v]=a[r];
        }
    }
    for(int u,i=0;i<q;++i) scanf("%d",&u), printf("%d\n",a[findroot(u)]);

}

Compilation message

synchronization.c: In function 'main':
synchronization.c:26:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d%d%d",&n,&m,&q);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.c:28:25: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     for(int i=1;i<n;++i)scanf("%d%d",e[i],e[i]+1),append(e[i][0],e[i][1]),append(e[i][1],e[i][0]);
      |                         ^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.c:31:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d",&ii);u=e[ii][0],v=e[ii][1];
      |         ^~~~~~~~~~~~~~~
synchronization.c:42:28: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     for(int u,i=0;i<q;++i) scanf("%d",&u), printf("%d\n",a[findroot(u)]);
      |                            ^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 4 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 6 ms 4956 KB Output is correct
8 Correct 6 ms 4840 KB Output is correct
9 Correct 6 ms 4956 KB Output is correct
10 Correct 71 ms 9212 KB Output is correct
11 Correct 69 ms 9308 KB Output is correct
12 Correct 60 ms 15192 KB Output is correct
13 Correct 41 ms 9308 KB Output is correct
14 Correct 52 ms 9300 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 12404 KB Output is correct
2 Correct 94 ms 12256 KB Output is correct
3 Correct 98 ms 15188 KB Output is correct
4 Correct 83 ms 15188 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 8 ms 5608 KB Output is correct
8 Correct 82 ms 15444 KB Output is correct
9 Correct 93 ms 15260 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 15444 KB Output is correct
2 Correct 168 ms 15564 KB Output is correct
3 Correct 172 ms 15840 KB Output is correct
4 Correct 205 ms 15700 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 9 ms 5020 KB Output is correct
7 Correct 102 ms 9552 KB Output is correct
8 Correct 81 ms 15440 KB Output is correct
9 Correct 62 ms 10064 KB Output is correct
10 Correct 81 ms 9868 KB Output is correct
11 Correct 122 ms 12876 KB Output is correct
12 Correct 115 ms 12784 KB Output is correct
13 Correct 174 ms 15740 KB Output is correct