Submission #4353631


Source Code Expand

Copy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)



//辺の情報を個別に持つタイプ
typedef struct edge{ll s,g;}E;
typedef struct graph{
	ll vcnt,ecnt;
	E  e[200010];//適宜変える
	ll id[100010];//適宜変える
}G;

int esort(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).s<(*q).s)return -1;
	if((*p).s>(*q).s)return  1;
	if((*p).g<(*q).g)return -1;
	return 1;
}

G g;
void readgraph(){
	//適宜変える
	ll n;
	scanf("%lld",&n);
	rep(i,0,n-1){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		x--,y--;
		g.e[2*i].s=x;
		g.e[2*i].g=y;
		g.e[2*i+1].s=y;
		g.e[2*i+1].g=x;
	}
	g.vcnt=n;
	g.ecnt=2*n-2;
	qsort(g.e,g.ecnt,sizeof(E),esort);

	int p=0;
	rep(i,0,g.vcnt){
		while(p<g.ecnt&&g.e[p].s<i)p++;
		g.id[i]=p;
	}
	g.id[g.vcnt]=g.ecnt;//一応番兵
}

ll que[100010];
ll temp[100010];
ll quecnt;

ll bfs(ll t){
	//tからbfsして最も遠い点の1つを返す
	quecnt=1;
	que[0]=t;
	
	rep(i,0,g.vcnt)temp[i]=0;
	temp[t]=1;
	
	ll last,M=0;
	while(quecnt){
		ll r=que[--quecnt];
		if(M<temp[r]){
			M=temp[r];
			last=r;
		}
		//rからbfs
		rep(i,g.id[r],g.id[r+1])if(!temp[g.e[i].g]){
			temp[g.e[i].g]=temp[r]+1;
			que[quecnt++]=g.e[i].g;
		}
	}
	return last;
}

ll len[100010];
void dfs(ll r){
	ll M=0;
	rep(i,g.id[r],g.id[r+1])if(!len[g.e[i].g]){
		len[g.e[i].g]=len[r]+1;
		dfs(g.e[i].g);
	}
}

ll f(ll*a){
	//まず直径を求めて、直径上に値を充てる
	//その後、直径上の点からdfsする
	ll s=bfs(0);
	ll t=bfs(s);
	
	//printf("%d %d\n",s,t);
	
	rep(i,0,g.vcnt)len[i]=0;
	ll R=temp[t]-1;//直径
	len[t]=R;
	
	ll cnt=0;
	while(t!=s){
		rep(i,g.id[t],g.id[t+1])if(temp[g.e[i].g]==R-cnt){
			t=g.e[i].g;
			++cnt;
			len[t]=max(R-cnt,cnt);
			break;
		}
	}
	
	//dfs
	rep(i,0,g.vcnt)if(len[i])dfs(i);
	rep(i,0,g.vcnt)a[len[i]]++;
	return R;
}


ll a[100010];
ll b[100010];
ll bs[100010];

int main(){
	readgraph();
	ll RN=f(a);
	
	//rep(i,0,10)printf("%d ",a[i]);
	//printf("%d\n",RN);
	
	readgraph();
	ll RM=f(b);
	
	ll M=max(RN,RM);
	
	rep(i,1,100010){
		bs[i]=b[i]*i+bs[i-1];
		b[i]+=b[i-1];
		//b[i]=[0,i]の個数 !!閉区間!!
	}
	
	ll ans=0;
	//max(M,x+y+1)
	rep(x,1,100010){
		//yがM-x-1以下ならM、それよりおおきいならそのまま
		ans+=(b[max(0,M-x-1)]*M+(bs[100005]-bs[max(0,M-x-1)]+(b[100005]-b[max(0,M-x-1)])*(x+1)))*a[x];
	}
	printf("%lld",ans);
}

Submission Info

Submission Time
Task B - Bonsai Grafting
User kyopro_friends
Language C (GCC 5.4.1)
Score 700
Code Size 3178 Byte
Status
Exec Time 133 ms
Memory 11588 KB

Compile Error

./Main.c: In function ‘readgraph’:
./Main.c:42:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ^
./Main.c:45:3: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&x,&y);
   ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
× 2
× 42
Set Name Test Cases
Sample 01.txt, 02.txt
All 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 3 ms 7552 KB
02.txt 3 ms 7552 KB
11.txt 3 ms 7552 KB
12.txt 3 ms 7552 KB
13.txt 3 ms 7552 KB
14.txt 3 ms 7552 KB
15.txt 3 ms 7552 KB
16.txt 3 ms 7552 KB
17.txt 3 ms 7552 KB
18.txt 3 ms 7552 KB
19.txt 3 ms 7552 KB
20.txt 3 ms 7552 KB
21.txt 130 ms 11460 KB
22.txt 125 ms 11460 KB
23.txt 131 ms 11460 KB
24.txt 131 ms 11460 KB
25.txt 121 ms 11460 KB
26.txt 127 ms 11460 KB
27.txt 127 ms 11460 KB
28.txt 133 ms 11460 KB
29.txt 133 ms 11460 KB
30.txt 132 ms 11460 KB
31.txt 129 ms 11460 KB
32.txt 125 ms 11460 KB
33.txt 131 ms 11460 KB
34.txt 130 ms 11460 KB
35.txt 120 ms 11460 KB
36.txt 127 ms 11460 KB
37.txt 127 ms 11460 KB
38.txt 133 ms 11460 KB
39.txt 133 ms 11588 KB
40.txt 132 ms 11460 KB
41.txt 67 ms 9468 KB
42.txt 66 ms 8388 KB
43.txt 68 ms 9468 KB
44.txt 66 ms 8388 KB
45.txt 62 ms 9468 KB
46.txt 62 ms 8388 KB
47.txt 68 ms 9468 KB
48.txt 68 ms 8388 KB
49.txt 68 ms 9468 KB
50.txt 67 ms 8388 KB