Submission #936974

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
936974	2024-03-03 07:20:53	sleepntsheep	Synchronization (JOI13_synchronization)	C11	100 / 100	205 ms	15840 KiB

synchronization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

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