Submission #4353774


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

#define PI 3.141592653589793238462
struct pnt{double x,y;static double eps;pnt(void){}pnt(double a,double b){x=a;y=b;}void set(double a,double b){x=a;y=b;}pnt&operator+=(pnt a){x+=a.x;y+=a.y;return*this;}pnt&operator-=(pnt a){x-=a.x;y-=a.y;return*this;}pnt&operator*=(pnt a){pnt p=*this;x=p.x*a.x-p.y*a.y;y=p.x*a.y+p.y*a.x;return*this;}pnt operator+(pnt a){return pnt(*this)+=a;}pnt operator-(pnt a){return pnt(*this)-=a;}pnt operator*(pnt a){return pnt(*this)*=a;}};
double pnt::eps = 1e-10;

char memarr[100000000];
void *mem;
char wmemarr[100000000];
void *wmem;

struct graph{
  int N, *es, **edge;

  void setEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
    int i;
    N = N__;
    es = (int*)(*mem);
    edge = (int**)(es+N);
    edge[0] = (int*)(edge+N);
    rep(i,N) es[i] = 0;
    rep(i,M) es[A[i]]++, es[B[i]]++;
    REP(i,1,N) edge[i] = edge[i-1] + es[i-1];
    (*mem) = edge[N-1] + es[N-1];
    rep(i,N) es[i] = 0;
    rep(i,M) edge[A[i]][es[A[i]]++] = B[i], edge[B[i]][es[B[i]]++] = A[i];
  }

  void setDirectEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
    int i;
    N = N__;
    es = (int*)(*mem);
    edge = (int**)(es+N);
    edge[0] = (int*)(edge+N);
    rep(i,N) es[i] = 0;
    rep(i,M) es[A[i]]++;
    REP(i,1,N) edge[i] = edge[i-1] + es[i-1];
    (*mem) = edge[N-1] + es[N-1];
    rep(i,N) es[i] = 0;
    rep(i,M) edge[A[i]][es[A[i]]++] = B[i];
  }

  graph reverse(void **mem = &wmem){
    int i, j, k;
    graph g;

    g.N = N;
    g.es = (int*)(*mem);
    g.edge = (int**)(g.es + N);
    g.edge[0] = (int*)(g.edge + N);

    rep(i,N) g.es[i] = 0;
    rep(i,N) rep(j,es[i]) g.es[edge[i][j]]++;

    REP(i,1,N) g.edge[i] = g.edge[i-1] + g.es[i-1];
    *mem = g.edge[N-1] + g.es[N-1];

    rep(i,N) g.es[i] = 0;
    rep(i,N) rep(j,es[i]){
      k = edge[i][j];
      g.edge[k][g.es[k]++] = i;
    }

    return g;
  }

  graph reduce(int tn, int ind[], int self_e = 0, int dep_e = 0, void **mem = &wmem){
    int i, j, k, M = 0;
    int x, y;
    graph g;
    pair<int,int> *A;

    rep(i,N) M += es[i];
    A = (pair<int,int>*)((int*)((int**)(*mem) + tn) + tn + M);

    M = 0;
    rep(i,N){
      x = ind[i];
      if(x < 0) continue;
      rep(j,es[i]){
        y = ind[edge[i][j]];
        if(y < 0) continue;
        if(self_e==0 && x==y) continue;
        A[M++] = make_pair(x, y);
      }
    }

    if(dep_e==0){
      sort(A, A+M);
      k = 0;
      rep(i,M){
        if(k && A[k-1]==A[i]) continue;
        A[k++] = A[i];
      }
      M = k;
    }

    g.N = tn;
    g.es = (int*)(*mem);
    g.edge = (int**)(g.es + tn);
    g.edge[0] = (int*)(g.edge + tn);

    rep(i,tn) g.es[i] = 0;
    rep(i,M) g.es[A[i].first]++;

    REP(i,1,tn) g.edge[i] = g.edge[i-1] + g.es[i-1];
    *mem = g.edge[tn-1] + g.es[tn-1];

    rep(i,tn) g.es[i] = 0;
    rep(i,M){
      j = A[i].first;
      k = A[i].second;
      g.edge[j][g.es[j]++] = k;
    }
    return g;
  }

  void getDist(int root, int res[], void *mem = wmem){
    int i,j,k,*q,s,z;
    q=(int*)mem;
    rep(i,N)res[i]=-1;
    res[root]=0;
    s=0;
    z=1;
    q[0]=root;
    while(z){
      i=q[s++];
      z--;
      rep(j,es[i]){
        k=edge[i][j];
        if(res[k]>=0)continue;
        res[k]=res[i]+1;
        q[s+z++]=k;
      }
    }
  }


  inline int sccDFS(int num[], int st, int mx){
    int i,j;
    num[st]=-2;
    rep(i,es[st]) {
      j=edge[st][i]; if(num[j]==-1) mx=sccDFS(num,j,mx);
    }
    num[st]=mx; return mx+1;
  }
  
  int scc(int res[], void *mem = wmem){
    int i, j, k, ret=0;
    graph r;
    int *st, st_size, *num, *nrv;
    
    r = reverse(&mem);
    st = (int*)mem; num = st+N; nrv = num + N;
    
    rep(i,N) res[i] = num[i] = -1;
    k = 0;
    rep(i,N) if(num[i]==-1) k = sccDFS(num,i,k);
    rep(i,N) nrv[num[i]] = i;
    
    for(k=N-1;k>=0;k--) {
      i=nrv[k]; if(res[i]>=0)continue;
      res[i]=ret; st_size=0; st[st_size++]=i;
      while(st_size){
        i=st[--st_size];
        rep(j,r.es[i])
          if(res[r.edge[i][j]]==-1) res[r.edge[i][j]]=ret, st[st_size++]=r.edge[i][j];
      }
      ret++;
    }
    
    return ret;
  }



  inline void bccDFS(int v, int u, int *res, int *rt, int &rts, int *S, int &Ss, int *inS, int *num, int &tm){
    int i, k;
    
    num[v] = ++tm;
    S[Ss++] = v; inS[v] = 1;
    rt[rts++] = v;
    rep(i, es[v]){
      int w = edge[v][i];
      if(!num[w]){
        bccDFS(w, v, res, rt, rts, S, Ss, inS, num, tm);
      } else if(u != w && inS[w]){
        while(num[rt[rts-1]] > num[w]) rts--;
      }
    }
    
    if(v == rt[rts-1]){
      k = S[Ss-1];
      for(;;){
        int w = S[--Ss];
        inS[w] = 0;
        res[w] = k;
        if(v==w) break;
      }
      rts--;
    }
  }

  int bcc(int res[], void *mem=wmem){
    int i, k;
    int *rt, *S, *num, *inS;
    pair<int,int> *arr;
    int rts = 0, Ss = 0, tm = 0;
    
    num = (int*)mem;
    rt = num + N;
    S = rt + N;
    inS = S + N;
    
    memset(num, 0, sizeof(int)*N);
    memset(inS, 0, sizeof(int)*N);
    rep(i,N) if(!num[i]) bccDFS(i, N, res, rt, rts, S, Ss, inS, num, tm);
    
    arr = (pair<int,int>*)mem;
    rep(i,N) arr[i].first = res[i], arr[i].second = i;
    sort(arr, arr+N);
    k = 0;
    rep(i,N){
      if(i && arr[i].first != arr[i-1].first) k++;
      res[arr[i].second] = k;
    }
    return k+1;
  }
};



void fft(int n, pnt x[], void *mem){int i,j,I,J,K,s=1;double t=2*PI/n,p;pnt w,v,u,a,b,c,d,A,B,C,D,*y=(pnt*)mem;while(n>2){I=n/4;J=I+I;K=I+J;rep(i,I){w=pnt(cos(i*t),-sin(i*t));v=w*w;u=w*v;rep(j,s)a=x[j+s*i],b=x[j+s*(i+I)],c=x[j+s*(i+J)],d=x[j+s*(i+K)],A=a+c,B=a-c,C=b+d,D=b-d,p=D.y,D.y=D.x,D.x=-p,y[j+s*4*i]=A+C,y[j+s*(4*i+1)]=w*(B-D),y[j+s*(4*i+2)]=v*(A-C),y[j+s*(4*i+3)]=u*(B+D);}n/=4;s*=4;t*=4;swap(x,y);}if(n==2){rep(i,s)y[i]=x[i]+x[i+s],y[i+s]=x[i]-x[i+s];n/=2;s*=2;t*=2;swap(x,y);}rep(i,s)y[i]=x[i];}
void fftinv(int n, pnt x[], void *mem){int i,j,I,J,K,s=1;double t=2*PI/n,p;pnt w,v,u,a,b,c,d,A,B,C,D,*y=(pnt*)mem;while(n>2){I=n/4;J=I+I;K=I+J;rep(i,I){w=pnt(cos(i*t),sin(i*t));v=w*w;u=w*v;rep(j,s)a=x[j+s*i],b=x[j+s*(i+I)],c=x[j+s*(i+J)],d=x[j+s*(i+K)],A=a+c,B=a-c,C=b+d,D=b-d,p=D.y,D.y=D.x,D.x=-p,y[j+s*4*i]=A+C,y[j+s*(4*i+1)]=w*(B+D),y[j+s*(4*i+2)]=v*(A-C),y[j+s*(4*i+3)]=u*(B-D);}n/=4;s*=4;t*=4;swap(x,y);}if(n==2){rep(i,s)y[i]=x[i]+x[i+s],y[i+s]=x[i]-x[i+s];n/=2;s*=2;t*=2;swap(x,y);}rep(i,s)y[i]=x[i];}
void convolution(double A[], int As, double B[], int Bs, double res[], int Rs, void *mem){int i,n,k;double m;pnt*a,*b;n=max(As+Bs,Rs);for(k=1;k<n;k*=2);a=(pnt*)mem;b=a+k;mem=b+k;rep(i,As)a[i].set(A[i],0);REP(i,As,k)a[i].set(0,0);rep(i,Bs)b[i].set(B[i],0);REP(i,Bs,k)b[i].set(0,0);fft(k,a,mem);fft(k,b,mem);rep(i,k)a[i]*=b[i];fftinv(k,a,mem);m=1.0/k;rep(i,Rs)res[i]=a[i].x*m;}

int N1, N2;
int A1[100000], B1[100000];
int A2[100000], B2[100000];

int dd1[100000], dd2[100000], d[100000];
int r1, r2;
int d1[1000000], d2[1000000];
double h1[1000000], h2[1000000], h[1000000];



int main(){
  int i, j, k, nn, r;
  ll res,cnt;
  graph g1, g2;

  mem = memarr;
  wmem = wmemarr;

  reader(&N1);
  rep(i,N1-1) reader(A1+i,B1+i);
  reader(&N2);
  rep(i,N2-1) reader(A2+i,B2+i);

  rep(i,N1-1) A1[i]--, B1[i]--;
  rep(i,N2-1) A2[i]--, B2[i]--;

  g1.setEdge(N1, N1-1, A1, B1);
  g2.setEdge(N2, N2-1, A2, B2);

  nn = (N1 + N2 + 10);

  g1.getDist(0,d);
  rep(i,N1) d1[i] = max(d1[i],d[i]);
  k = 0;
  rep(i,N1) if(d[k] < d[i]) k = i;
  g1.getDist(k,d);
  rep(i,N1) d1[i] = max(d1[i],d[i]);
  k = 0;
  rep(i,N1) if(d[k] < d[i]) k = i;
  g1.getDist(k,d);
  rep(i,N1) d1[i] = max(d1[i],d[i]);

  g2.getDist(0,d);
  rep(i,N2) d2[i] = max(d2[i],d[i]);
  k = 0;
  rep(i,N2) if(d[k] < d[i]) k = i;
  g2.getDist(k,d);
  rep(i,N2) d2[i] = max(d2[i],d[i]);
  k = 0;
  rep(i,N2) if(d[k] < d[i]) k = i;
  g2.getDist(k,d);
  rep(i,N2) d2[i] = max(d2[i],d[i]);

  rep(i,N1) h1[d1[i]]++;
  rep(i,N2) h2[d2[i]]++;
  convolution(h1, N1+1, h2, N2+1, h, nn, mem);

  r = 0;
  rep(i,N1) r = max(r,d1[i]);
  rep(i,N2) r = max(r,d2[i]);

  res = 0;

//  rep(i,N1) writerLn(i,d1[i]);
//  rep(i,N2) writerLn(i,d2[i]);
  

  rep(i,nn){
    cnt = (ll)(h[i]+0.5);
    res += max(i+1,r) * cnt;
  }
  
  writerLn(res);

  return 0;
}

Submission Info

Submission Time
Task B - Bonsai Grafting
User LayCurse
Language C++14 (GCC 5.4.1)
Score 700
Code Size 10519 Byte
Status
Exec Time 73 ms
Memory 34560 KB

Compile Error

./Main.cpp: In function ‘void reader(double*)’:
./Main.cpp:15:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void reader(double *x){scanf("%lf",x);}
                                      ^

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 01.txt, 02.txt
All 700 / 700 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt
Case Name Status Exec Time Memory
01.txt 5 ms 14848 KB
02.txt 4 ms 14592 KB
11.txt 4 ms 14592 KB
12.txt 4 ms 14592 KB
13.txt 4 ms 14592 KB
14.txt 4 ms 14592 KB
15.txt 4 ms 14592 KB
16.txt 4 ms 14592 KB
17.txt 4 ms 14592 KB
18.txt 4 ms 14592 KB
19.txt 4 ms 14592 KB
20.txt 4 ms 14592 KB
21.txt 71 ms 32640 KB
22.txt 64 ms 32512 KB
23.txt 69 ms 32512 KB
24.txt 71 ms 34560 KB
25.txt 59 ms 32512 KB
26.txt 64 ms 32512 KB
27.txt 66 ms 34560 KB
28.txt 69 ms 32512 KB
29.txt 71 ms 34560 KB
30.txt 73 ms 34560 KB
31.txt 69 ms 32512 KB
32.txt 64 ms 32512 KB
33.txt 69 ms 32512 KB
34.txt 71 ms 34560 KB
35.txt 59 ms 32512 KB
36.txt 65 ms 32512 KB
37.txt 66 ms 34560 KB
38.txt 70 ms 32512 KB
39.txt 71 ms 34560 KB
40.txt 73 ms 34560 KB
41.txt 38 ms 23552 KB
42.txt 37 ms 23552 KB
43.txt 37 ms 23552 KB
44.txt 37 ms 23552 KB
45.txt 33 ms 23552 KB
46.txt 32 ms 23552 KB
47.txt 40 ms 25600 KB
48.txt 38 ms 23552 KB
49.txt 40 ms 25600 KB
50.txt 39 ms 23552 KB