oj.uz

Submission #677206

# Submission time Handle Problem Language Result Execution time Memory
677206 2023-01-02T14:37:17 Z SanguineChameleon Hard route (IZhO17_road) C++17
100 / 100
 1006 ms 198860 KB 
// BEGIN BOILERPLATE CODE

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

#ifdef KAMIRULEZ
	const bool kami_loc = true;
	const long long kami_seed = 69420;
#else
	const bool kami_loc = false;
	const long long kami_seed = chrono::steady_clock::now().time_since_epoch().count();
#endif

const string kami_fi = "kamirulez.inp";
const string kami_fo = "kamirulez.out";
mt19937_64 kami_gen(kami_seed);

long long rand_range(long long rmin, long long rmax) {
	uniform_int_distribution<long long> rdist(rmin, rmax);
	return rdist(kami_gen);
}

long double rand_real(long double rmin, long double rmax) {
	uniform_real_distribution<long double> rdist(rmin, rmax);
	return rdist(kami_gen);
}

void file_io(string fi, string fo) {
	if (fi != "" && (!kami_loc || fi == kami_fi)) {
		freopen(fi.c_str(), "r", stdin);
	}
	if (fo != "" && (!kami_loc || fo == kami_fo)) {
		freopen(fo.c_str(), "w", stdout);
	}
}

void set_up() {
	if (kami_loc) {
		file_io(kami_fi, kami_fo);
	}
	ios_base::sync_with_stdio(0);
	cin.tie(0);
}

void just_do_it();

void just_exec_it() {
	if (kami_loc) {
		auto pstart = chrono::steady_clock::now();
		just_do_it();
		auto pend = chrono::steady_clock::now();
		long long ptime = chrono::duration_cast<chrono::milliseconds>(pend - pstart).count();
		string bar(50, '=');
		cout << '\n' << bar << '\n';
		cout << "Time: " << ptime << " ms" << '\n';
	}
	else {
		just_do_it();
	}
}

int main() {
	set_up();
	just_exec_it();
	return 0;
}

// END BOILERPLATE CODE

// BEGIN MAIN CODE

const int ms = 5e5 + 20;
const int inf = 1e9 + 20;
vector<int> adj[ms];
pair<long long, long long> res = {0, 1};

pair<int, int> operator+(pair<int, int> x, int d) {
	return {x.first + d, x.second};
}

pair<long long, long long> max(pair<long long, long long> x, pair<long long, long long> y) {
	if (x.first > y.first) {
		return x;
	}
	else if (x.first < y.first) {
		return y;
	}
	else {
		return {x.first, x.second + y.second};
	}
}

struct chunk {
	int sz = 0;
	long long s1 = 0;
	long long s2 = 0;

	void add(int x) {
		sz++;
		s1 += x;
		s2 += 1LL * x * x;
	}

	void rem(int x) {
		sz--;
		s1 -= x;
		s2 -= 1LL * x * x;
	}

	long long get1() {
		return s1;
	}

	long long get2() {
		return (s1 * s1 - s2) / 2;
	}
};

struct group {
	map<int, chunk, greater<int>> f;

	void add(pair<int, int> x) {
		f[x.first].add(x.second);
	}

	void rem(pair<int, int> x) {
		auto it = f.find(x.first);
		it->second.rem(x.second);
		if (it->second.sz == 0) {
			f.erase(it);
		}
	}

	pair<int, int> best() {
		return {f.begin()->first, f.begin()->second.s1};
	}

	void calc() {
		auto it = f.begin();
		if (it == f.end()) {
			return;
		}
		int x1 = it->first;
		if (x1 == 0) {
			return;
		}
		chunk &p1 = it->second;
		if (p1.sz >= 3) {
			res = max(res, make_pair(1LL * x1 * (x1 + x1), p1.get2()));
			return;
		}
		it++;
		if (it == f.end()) {
			return;
		}
		int x2 = it->first;
		if (x2 == 0) {
			return;
		}
		chunk &p2 = it->second;
		if (p1.sz >= 2) {
			res = max(res, make_pair(1LL * x1 * (x1 + x2), p1.get1() * p2.get1()));
			return;
		}
		if (p2.sz >= 2) {
			res = max(res, make_pair(1LL * x1 * (x2 + x2), p2.get2()));
			return;
		}
		it++;
		if (it == f.end()) {
			return;
		}
		int x3 = it->first;
		if (x3 == 0) {
			return;
		}
		chunk &p3 = it->second;
		res = max(res, make_pair(1LL * x1 * (x2 + x3), p2.get1() * p3.get1()));
		return;
	}
};

group g[ms];

void dfs1(int u, int pr) {
	g[u].add({0, 1});
	for (auto v: adj[u]) {
		if (v != pr) {
			dfs1(v, u);
			g[u].add(g[v].best() + 1);
		}
	}
}

void dfs2(int u, int pr) {
	g[u].calc();
	for (auto v: adj[u]) {
		if (v != pr) {
			g[u].rem(g[v].best() + 1);
			g[v].add(g[u].best() + 1);
			dfs2(v, u);
			g[v].rem(g[u].best() + 1);
			g[u].add(g[v].best() + 1);
		}
	}
}

void just_do_it() {
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs1(1, -1);
	dfs2(1, -1);
	cout << res.first << " " << res.second;
}

// END MAIN CODE

Compilation message

road.cpp: In function 'void file_io(std::string, std::string)':
road.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   freopen(fi.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
road.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen(fo.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35548 KB Output is correct
2 Correct 17 ms 35540 KB Output is correct
3 Correct 17 ms 35540 KB Output is correct
4 Correct 17 ms 35548 KB Output is correct
5 Correct 17 ms 35480 KB Output is correct
6 Correct 21 ms 35480 KB Output is correct
7 Correct 17 ms 35540 KB Output is correct
8 Correct 17 ms 35556 KB Output is correct
9 Correct 21 ms 35572 KB Output is correct
10 Correct 16 ms 35532 KB Output is correct
11 Correct 16 ms 35560 KB Output is correct
12 Correct 17 ms 35488 KB Output is correct
13 Correct 18 ms 35452 KB Output is correct
14 Correct 18 ms 35540 KB Output is correct
15 Correct 17 ms 35464 KB Output is correct
16 Correct 17 ms 35512 KB Output is correct
17 Correct 17 ms 35552 KB Output is correct
18 Correct 17 ms 35504 KB Output is correct
19 Correct 19 ms 35544 KB Output is correct
20 Correct 16 ms 35524 KB Output is correct
21 Correct 20 ms 35568 KB Output is correct
22 Correct 17 ms 35548 KB Output is correct
23 Correct 17 ms 35540 KB Output is correct
24 Correct 17 ms 35540 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35548 KB Output is correct
2 Correct 17 ms 35540 KB Output is correct
3 Correct 17 ms 35540 KB Output is correct
4 Correct 17 ms 35548 KB Output is correct
5 Correct 17 ms 35480 KB Output is correct
6 Correct 21 ms 35480 KB Output is correct
7 Correct 17 ms 35540 KB Output is correct
8 Correct 17 ms 35556 KB Output is correct
9 Correct 21 ms 35572 KB Output is correct
10 Correct 16 ms 35532 KB Output is correct
11 Correct 16 ms 35560 KB Output is correct
12 Correct 17 ms 35488 KB Output is correct
13 Correct 18 ms 35452 KB Output is correct
14 Correct 18 ms 35540 KB Output is correct
15 Correct 17 ms 35464 KB Output is correct
16 Correct 17 ms 35512 KB Output is correct
17 Correct 17 ms 35552 KB Output is correct
18 Correct 17 ms 35504 KB Output is correct
19 Correct 19 ms 35544 KB Output is correct
20 Correct 16 ms 35524 KB Output is correct
21 Correct 20 ms 35568 KB Output is correct
22 Correct 17 ms 35548 KB Output is correct
23 Correct 17 ms 35540 KB Output is correct
24 Correct 17 ms 35540 KB Output is correct
25 Correct 20 ms 36656 KB Output is correct
26 Correct 20 ms 36804 KB Output is correct
27 Correct 20 ms 36692 KB Output is correct
28 Correct 26 ms 36796 KB Output is correct
29 Correct 24 ms 36692 KB Output is correct
30 Correct 21 ms 36692 KB Output is correct
31 Correct 24 ms 36720 KB Output is correct
32 Correct 20 ms 36724 KB Output is correct
33 Correct 23 ms 36792 KB Output is correct
34 Correct 21 ms 36768 KB Output is correct
35 Correct 22 ms 36844 KB Output is correct
36 Correct 19 ms 36796 KB Output is correct
37 Correct 20 ms 36820 KB Output is correct
38 Correct 21 ms 37136 KB Output is correct
39 Correct 21 ms 36656 KB Output is correct
40 Correct 21 ms 36612 KB Output is correct
41 Correct 21 ms 36684 KB Output is correct
42 Correct 20 ms 36472 KB Output is correct
43 Correct 21 ms 36456 KB Output is correct
44 Correct 23 ms 36556 KB Output is correct
45 Correct 20 ms 36376 KB Output is correct
46 Correct 19 ms 36180 KB Output is correct
47 Correct 19 ms 36268 KB Output is correct
48 Correct 19 ms 36068 KB Output is correct

Subtask #3
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35548 KB Output is correct
2 Correct 17 ms 35540 KB Output is correct
3 Correct 17 ms 35540 KB Output is correct
4 Correct 17 ms 35548 KB Output is correct
5 Correct 17 ms 35480 KB Output is correct
6 Correct 21 ms 35480 KB Output is correct
7 Correct 17 ms 35540 KB Output is correct
8 Correct 17 ms 35556 KB Output is correct
9 Correct 21 ms 35572 KB Output is correct
10 Correct 16 ms 35532 KB Output is correct
11 Correct 16 ms 35560 KB Output is correct
12 Correct 17 ms 35488 KB Output is correct
13 Correct 18 ms 35452 KB Output is correct
14 Correct 18 ms 35540 KB Output is correct
15 Correct 17 ms 35464 KB Output is correct
16 Correct 17 ms 35512 KB Output is correct
17 Correct 17 ms 35552 KB Output is correct
18 Correct 17 ms 35504 KB Output is correct
19 Correct 19 ms 35544 KB Output is correct
20 Correct 16 ms 35524 KB Output is correct
21 Correct 20 ms 35568 KB Output is correct
22 Correct 17 ms 35548 KB Output is correct
23 Correct 17 ms 35540 KB Output is correct
24 Correct 17 ms 35540 KB Output is correct
25 Correct 20 ms 36656 KB Output is correct
26 Correct 20 ms 36804 KB Output is correct
27 Correct 20 ms 36692 KB Output is correct
28 Correct 26 ms 36796 KB Output is correct
29 Correct 24 ms 36692 KB Output is correct
30 Correct 21 ms 36692 KB Output is correct
31 Correct 24 ms 36720 KB Output is correct
32 Correct 20 ms 36724 KB Output is correct
33 Correct 23 ms 36792 KB Output is correct
34 Correct 21 ms 36768 KB Output is correct
35 Correct 22 ms 36844 KB Output is correct
36 Correct 19 ms 36796 KB Output is correct
37 Correct 20 ms 36820 KB Output is correct
38 Correct 21 ms 37136 KB Output is correct
39 Correct 21 ms 36656 KB Output is correct
40 Correct 21 ms 36612 KB Output is correct
41 Correct 21 ms 36684 KB Output is correct
42 Correct 20 ms 36472 KB Output is correct
43 Correct 21 ms 36456 KB Output is correct
44 Correct 23 ms 36556 KB Output is correct
45 Correct 20 ms 36376 KB Output is correct
46 Correct 19 ms 36180 KB Output is correct
47 Correct 19 ms 36268 KB Output is correct
48 Correct 19 ms 36068 KB Output is correct
49 Correct 776 ms 155912 KB Output is correct
50 Correct 795 ms 160448 KB Output is correct
51 Correct 781 ms 164152 KB Output is correct
52 Correct 751 ms 150860 KB Output is correct
53 Correct 729 ms 162020 KB Output is correct
54 Correct 716 ms 166084 KB Output is correct
55 Correct 774 ms 155980 KB Output is correct
56 Correct 729 ms 160424 KB Output is correct
57 Correct 814 ms 170828 KB Output is correct
58 Correct 780 ms 165832 KB Output is correct
59 Correct 774 ms 165772 KB Output is correct
60 Correct 755 ms 163452 KB Output is correct
61 Correct 1006 ms 198860 KB Output is correct
62 Correct 977 ms 187568 KB Output is correct
63 Correct 993 ms 154536 KB Output is correct
64 Correct 966 ms 146640 KB Output is correct
65 Correct 925 ms 141620 KB Output is correct
66 Correct 884 ms 139044 KB Output is correct
67 Correct 882 ms 137520 KB Output is correct
68 Correct 864 ms 136932 KB Output is correct
69 Correct 907 ms 136600 KB Output is correct
70 Correct 842 ms 136376 KB Output is correct
71 Correct 848 ms 136028 KB Output is correct
72 Correct 848 ms 136480 KB Output is correct
73 Correct 1004 ms 135940 KB Output is correct
74 Correct 843 ms 135104 KB Output is correct
75 Correct 829 ms 132880 KB Output is correct
76 Correct 829 ms 129028 KB Output is correct
77 Correct 737 ms 117876 KB Output is correct
78 Correct 482 ms 99520 KB Output is correct