oj.uz

Submission #936973

# Submission time Handle Problem Language Result Execution time Memory
936973 2024-03-03T07:18:05 Z sleepntsheep Synchronization (JOI13_synchronization) C++17
100 / 100
 168 ms 18332 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.cpp: In function 'int main()':
synchronization.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
synchronization.cpp:28:30: warning: ignoring return value of 'int scanf(const char*, ...)' 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.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d",&ii);u=e[ii][0],v=e[ii][1];
      |         ~~~~~^~~~~~~~~~
synchronization.cpp:42:33: warning: ignoring return value of 'int scanf(const char*, ...)' 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 4 ms 4696 KB Output is correct
2 Correct 2 ms 4516 KB Output is correct
3 Correct 1 ms 4516 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 1 ms 4524 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 6 ms 5212 KB Output is correct
8 Correct 6 ms 5052 KB Output is correct
9 Correct 6 ms 5048 KB Output is correct
10 Correct 73 ms 11444 KB Output is correct
11 Correct 70 ms 11348 KB Output is correct
12 Correct 61 ms 17488 KB Output is correct
13 Correct 42 ms 11348 KB Output is correct
14 Correct 54 ms 11028 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 14356 KB Output is correct
2 Correct 80 ms 14228 KB Output is correct
3 Correct 73 ms 16992 KB Output is correct
4 Correct 72 ms 16900 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 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 4696 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4440 KB Output is correct
7 Correct 9 ms 5856 KB Output is correct
8 Correct 79 ms 18332 KB Output is correct
9 Correct 84 ms 18240 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 18260 KB Output is correct
2 Correct 168 ms 17836 KB Output is correct
3 Correct 152 ms 18140 KB Output is correct
4 Correct 151 ms 18152 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4516 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4596 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4440 KB Output is correct
6 Correct 8 ms 5464 KB Output is correct
7 Correct 101 ms 12244 KB Output is correct
8 Correct 80 ms 18260 KB Output is correct
9 Correct 63 ms 12436 KB Output is correct
10 Correct 88 ms 12228 KB Output is correct
11 Correct 102 ms 15596 KB Output is correct
12 Correct 103 ms 15600 KB Output is correct
13 Correct 157 ms 18164 KB Output is correct