Submission #4353137


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;
	while(quecnt){
		ll r=que[--quecnt];
		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);
	
	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);
	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("%d",ans);
}

Submission Info

Submission Time
Task B - Bonsai Grafting
User kyopro_friends
Language C (GCC 5.4.1)
Score 0
Code Size 3045 Byte
Status
Exec Time 134 ms
Memory 14788 KB

Compile Error

./Main.c: In function ‘main’:
./Main.c:149:9: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘long long int’ [-Wformat=]
  printf("%d",ans);
         ^
./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);
   ^

Test Cases

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