Submission #936973

#	Time	Username	Problem	Language	Result	Execution time	Memory
936973		sleepntsheep	Synchronization (JOI13_synchronization)	C++17	100 / 100	168 ms	18332 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40