Submission #4352777


Source Code Expand

Copy
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int N[2];
vector<int> tree[2][101010]; int D[2][101010], diam[2];

void load_tree(int &N, vector<int> *tr)
{
	scanf("%d", &N);
	for (int i = 0; i < N - 1; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		--u; --v;
		tr[u].push_back(v);
		tr[v].push_back(u);
	}
}

int chd[101010];

int dfs(int t, int p, int r = -1)
{
	int v = 0;
	for (int q : tree[t][p]) if (q != r) {
		v = max(v, dfs(t, q, p) + 1);
	}
	return chd[p] = v;
}
void dfs2(int t, int p, int fd, int r = -1)
{
	int chs1 = 0, chs2 = 0;
	for (int q : tree[t][p]) if (q != r) {
		int tmp = chd[q] + 1;
		if (chs1 < tmp) {
			chs2 = chs1;
			chs1 = tmp;
		} else if (chs2 < tmp) {
			chs2 = tmp;
		}
	}
	for (int q : tree[t][p]) if (q != r) {
		int nxfd = (chd[q] + 1 == chs1 ? chs2 : chs1);
		nxfd = max(nxfd, fd);
		dfs2(t, q, nxfd + 1, p);
	}
	D[t][p] = max(fd, chs1);
}

void computeD(int t)
{
	fill(chd, chd + N[t], 0);
	dfs(t, 0);
	dfs2(t, 0, 0);
	int v = 0;
	for (int i = 0; i < N[t]; ++i) v = max(v, D[t][i]);
	diam[t] = v;
}

int main()
{
	load_tree(N[0], tree[0]);
	load_tree(N[1], tree[1]);
	computeD(0);
	computeD(1);
	//for (int i = 0; i < N[0]; ++i) printf("%d: %d\n", i, D[0][i]);

	int A = N[0], B = N[1];
	vector<int> P, Q;
	for (int i = 0; i < A; ++i) P.push_back(D[0][i]);
	for (int i = 0; i < B; ++i) Q.push_back(D[1][i]);
	int base = max(diam[0], diam[1]) - 1;
	sort(P.begin(), P.end());
	sort(Q.begin(), Q.end());

	vector<i64> Qacc;
	Qacc.push_back(0LL);
	for (int i = 0; i < B; ++i) {
		i64 nxt = Qacc.back() + Q[i];
		Qacc.push_back(nxt);
	}

	i64 ret = 0;

	for (int i = 0; i < A; ++i) {
		int pt = lower_bound(Q.begin(), Q.end(), base - P[i]) - Q.begin();
		//printf("%d: %d %d a %lld\n", i, P[i], pt, (i64)pt * base + (i64)(B - pt) * P[i] + Qacc.back() - Qacc[pt]);
		ret += (i64)pt * base + (i64)(B - pt) * P[i] + Qacc.back() - Qacc[pt];
	}

	ret += (i64)A * B;
	printf("%lld\n", ret);

	return 0;
}

Submission Info

Submission Time
Task B - Bonsai Grafting
User semiexp
Language C++14 (GCC 5.4.1)
Score 700
Code Size 2350 Byte
Status
Exec Time 110 ms
Memory 21116 KB

Compile Error

./Main.cpp: In function ‘void load_tree(int&, std::vector<int>*)’:
./Main.cpp:22:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:25:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
                        ^

Test Cases

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 3 ms 4992 KB
02.txt 4 ms 4992 KB
11.txt 4 ms 4992 KB
12.txt 4 ms 4992 KB
13.txt 4 ms 4992 KB
14.txt 4 ms 4992 KB
15.txt 4 ms 4992 KB
16.txt 4 ms 4992 KB
17.txt 4 ms 4992 KB
18.txt 4 ms 4992 KB
19.txt 3 ms 4992 KB
20.txt 3 ms 4992 KB
21.txt 94 ms 14584 KB
22.txt 88 ms 14856 KB
23.txt 98 ms 14460 KB
24.txt 103 ms 19708 KB
25.txt 83 ms 14972 KB
26.txt 102 ms 14712 KB
27.txt 103 ms 19832 KB
28.txt 100 ms 14456 KB
29.txt 106 ms 19704 KB
30.txt 109 ms 20860 KB
31.txt 94 ms 14588 KB
32.txt 88 ms 14872 KB
33.txt 97 ms 14460 KB
34.txt 110 ms 21116 KB
35.txt 82 ms 15068 KB
36.txt 96 ms 14716 KB
37.txt 101 ms 18296 KB
38.txt 98 ms 14456 KB
39.txt 106 ms 19064 KB
40.txt 109 ms 19452 KB
41.txt 49 ms 10616 KB
42.txt 48 ms 9596 KB
43.txt 51 ms 10488 KB
44.txt 47 ms 9596 KB
45.txt 43 ms 10752 KB
46.txt 42 ms 9852 KB
47.txt 58 ms 16888 KB
48.txt 50 ms 9596 KB
49.txt 56 ms 14072 KB
50.txt 58 ms 13180 KB