답안 #887728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887728	2023-12-15T05:12:34 Z	beaboss	Hard route (IZhO17_road)	C++14	19 / 100	2000 ms	13404 KB

road

// // Source: https://oj.uz/problem/view/IZhO17_road
// // 

// #include "bits/stdc++.h"

// using namespace std;

// #define s second
// #define f first
// #define pb push_back

// typedef long long ll;

// typedef pair<ll, ll> pii;
// typedef vector<pii> vpii;

// typedef vector<ll> vi;

// #define FOR(i, a, b) for (ll i = (a); i<b; i++)

// bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }

// bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }

// const ll N = 5e5 + 10;

// vi adj[N];
// ll d[N], cnt[N];
// pii out[N];

// void dfs(ll cur, ll p = -1) {
// 	if (adj[cur].size() == 1 && p!=-1)cnt[cur]=1;

// 	for (auto val: adj[cur]) {
// 		if (val != p) {
// 			dfs(val, cur);
// 			if (ckmax(d[cur], d[val] + 1)) {
// 				cnt[cur] = cnt[val];
// 			} else if (d[cur] == d[val] + 1) cnt[cur] += cnt[val];

// 		}
// 	}
// }

// ll mx = 0;
// ll tot = 0;

// void dfs2(ll cur, ll p = -1) {
// 	vpii leaf;
// 	leaf.pb(out[cur]);

// 	for (auto val: adj[cur]) {
// 		if (val != p) leaf.pb({d[val]+1, cnt[val]});
// 	}

// 	sort(leaf.rbegin(), leaf.rend());
// 	// cout << cur << endl;
// 	// for (auto val: leaf) cout << val.f << val.s << ' ';
// 	// 	cout << endl;
// 	if (leaf.size() >= 3 && leaf[0].f * (leaf[1].f + leaf[2].f) >= mx) {
// 		ll res = 0;
// 		ll eq3 = 0;
// 		ll hardness = leaf[0].f * (leaf[1].f + leaf[2].f);
// 		// cout <
// 		for (auto val: leaf) if (val.f == leaf[2].f) eq3+=val.s;

// 		if (leaf[1].f == leaf[2].f) {
// 			res = eq3*eq3;
// 			for (auto val: leaf) if (val.f==leaf[2].f) res -= val.s*val.s;
// 			res /= 2;
// 		} else if (leaf[0].f == leaf[1].f) {
// 			res = eq3*(leaf[1].s+leaf[0].s);
// 		} else {
// 			res = eq3 * leaf[1].s;
// 		}

// 		if (ckmax(mx, hardness)) tot = res;
// 		else if (mx == hardness) tot += res;
// 	}


// 	ll num1 = 0;
// 	ll num2 = 0;
// 	for (auto val: adj[cur]) {
// 		if (d[val] + 1 == leaf[0].f) num1+=cnt[val];
// 		if (d[val] + 1 == leaf[1].f) num2+=cnt[val]; 
// 	}

// 	if (out[cur].f == leaf[0].f) num1 += out[cur].s;
// 	if (out[cur].f == leaf[1].f) num2 += out[cur].s;


// 	for (auto val: adj[cur]) {
// 		if (val != p) {
// 			if (d[val] + 1 == leaf[0].f && leaf[0].f == leaf[1].f) out[val] = {leaf[1].f+1, num1 - cnt[val]};
// 			else if (d[val] + 1 == leaf[0].f) out[val] = {leaf[1].f + 1, num2};
// 			else out[val] = {leaf[0].f + 1, num1};

// 			dfs2(val, cur);
// 		}
// 	}
// }

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	ll n;
// 	cin >> n;

// 	FOR(i, 1, n) {
// 		ll a, b;
// 		cin >> a >> b;
// 		adj[a].pb(b);
// 		adj[b].pb(a);
// 	}
// 	if (adj[1].size() == 1) out[1].s=1;
// 	dfs(1);
// 	dfs2(1);

// 	if (mx == 0 && tot == 0) tot=1;

// 	cout << mx << ' ' << tot << endl;



// }












#include "bits/stdc++.h"
 
using namespace std;
 
#define s second
#define f first
#define pb push_back
 
typedef long long ll;
 
typedef pair<int, int> pii;
const ll N = 5*1e5 + 10;
 
vector<ll> adj[N];
bool v[N];
bool visited[N];
int curdist = 0;
int maxd = 0;
ll maxi = 0;
ll nummaxi = 0;
 
void update(ll ans, ll numways) {
	if (ans > maxi) {
		maxi = ans;
		nummaxi = numways;
	} else if (ans == maxi) nummaxi += numways;
}
 
bool dfs(int cur, int target, int d) {
	if (cur == target) {
		v[cur]=true;
		curdist = d;
		return true;
	}
	// cout << cur << target << endl;
	visited[cur]=true;
	for (auto val: adj[cur]) {
		if (!visited[val]) {
 
			v[cur] = (dfs(val, target, d+ 1) || v[cur]);
		}
	}
	return v[cur];
}
 
 
 
void dfs2(int cur, int d) {
	visited[cur] = true;
	if (d > maxd) {
		maxd = d;
		// update(curdist * d, 1);
	}
 
	for (auto val: adj[cur]) {
		if (!visited[val] && !v[val]) dfs2(val, d+1);
	}
}
 
 
int main() {
	int n;
	cin >> n;
 
	for (ll i = 0; i < n -1; i++ ) {
		ll a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
 
	}
	vector<int> leaves;
	for (int i = 1; i <= n; i++) {
		if (adj[i].size() == 1) {
			leaves.push_back(i);
		}
	}
 
	for (int i = 0; i < leaves.size(); i++) {
		for (int j = i + 1; j < leaves.size(); j++) {
			int curans = 0;
			maxd = 0;
			curdist = 0;
			memset(v, false, sizeof v);
			memset(visited, false, sizeof visited);
			dfs(leaves[i], leaves[j], 0);
			memset(visited, false, sizeof visited);
			for (int i = 0; i < n; i++) {
				if (v[i]) {
 
					dfs2(i, 0);
				}
			}
 
			// cout << leaves[i] << leaves[j] << curdist << maxd << endl;
			update(curdist * maxd, 1);
 
		}
	}
	cout << maxi << ' ' << nummaxi << endl;
}

Compilation message

road.cpp: In function 'int main()':
road.cpp:218:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |  for (int i = 0; i < leaves.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
road.cpp:219:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |   for (int j = i + 1; j < leaves.size(); j++) {
      |                       ~~^~~~~~~~~~~~~~~
road.cpp:220:8: warning: unused variable 'curans' [-Wunused-variable]
  220 |    int curans = 0;
      |        ^~~~~~

Subtask #1

19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	13148 KB	Output is correct
2	Correct	4 ms	13148 KB	Output is correct
3	Correct	2 ms	13148 KB	Output is correct
4	Correct	2 ms	13148 KB	Output is correct
5	Correct	3 ms	13148 KB	Output is correct
6	Correct	3 ms	13148 KB	Output is correct
7	Correct	11 ms	13148 KB	Output is correct
8	Correct	8 ms	12988 KB	Output is correct
9	Correct	11 ms	13160 KB	Output is correct
10	Correct	10 ms	13148 KB	Output is correct
11	Correct	30 ms	13148 KB	Output is correct
12	Correct	31 ms	13148 KB	Output is correct
13	Correct	30 ms	13144 KB	Output is correct
14	Correct	30 ms	13148 KB	Output is correct
15	Correct	3 ms	13156 KB	Output is correct
16	Correct	3 ms	13148 KB	Output is correct
17	Correct	4 ms	13164 KB	Output is correct
18	Correct	3 ms	13148 KB	Output is correct
19	Correct	3 ms	13148 KB	Output is correct
20	Correct	3 ms	13148 KB	Output is correct
21	Correct	3 ms	13148 KB	Output is correct
22	Correct	3 ms	13148 KB	Output is correct
23	Correct	4 ms	12992 KB	Output is correct
24	Correct	108 ms	13148 KB	Output is correct

Subtask #2

0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	13148 KB	Output is correct
2	Correct	4 ms	13148 KB	Output is correct
3	Correct	2 ms	13148 KB	Output is correct
4	Correct	2 ms	13148 KB	Output is correct
5	Correct	3 ms	13148 KB	Output is correct
6	Correct	3 ms	13148 KB	Output is correct
7	Correct	11 ms	13148 KB	Output is correct
8	Correct	8 ms	12988 KB	Output is correct
9	Correct	11 ms	13160 KB	Output is correct
10	Correct	10 ms	13148 KB	Output is correct
11	Correct	30 ms	13148 KB	Output is correct
12	Correct	31 ms	13148 KB	Output is correct
13	Correct	30 ms	13144 KB	Output is correct
14	Correct	30 ms	13148 KB	Output is correct
15	Correct	3 ms	13156 KB	Output is correct
16	Correct	3 ms	13148 KB	Output is correct
17	Correct	4 ms	13164 KB	Output is correct
18	Correct	3 ms	13148 KB	Output is correct
19	Correct	3 ms	13148 KB	Output is correct
20	Correct	3 ms	13148 KB	Output is correct
21	Correct	3 ms	13148 KB	Output is correct
22	Correct	3 ms	13148 KB	Output is correct
23	Correct	4 ms	12992 KB	Output is correct
24	Correct	108 ms	13148 KB	Output is correct
25	Execution timed out	2058 ms	13404 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-

Subtask #3

0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	13148 KB	Output is correct
2	Correct	4 ms	13148 KB	Output is correct
3	Correct	2 ms	13148 KB	Output is correct
4	Correct	2 ms	13148 KB	Output is correct
5	Correct	3 ms	13148 KB	Output is correct
6	Correct	3 ms	13148 KB	Output is correct
7	Correct	11 ms	13148 KB	Output is correct
8	Correct	8 ms	12988 KB	Output is correct
9	Correct	11 ms	13160 KB	Output is correct
10	Correct	10 ms	13148 KB	Output is correct
11	Correct	30 ms	13148 KB	Output is correct
12	Correct	31 ms	13148 KB	Output is correct
13	Correct	30 ms	13144 KB	Output is correct
14	Correct	30 ms	13148 KB	Output is correct
15	Correct	3 ms	13156 KB	Output is correct
16	Correct	3 ms	13148 KB	Output is correct
17	Correct	4 ms	13164 KB	Output is correct
18	Correct	3 ms	13148 KB	Output is correct
19	Correct	3 ms	13148 KB	Output is correct
20	Correct	3 ms	13148 KB	Output is correct
21	Correct	3 ms	13148 KB	Output is correct
22	Correct	3 ms	13148 KB	Output is correct
23	Correct	4 ms	12992 KB	Output is correct
24	Correct	108 ms	13148 KB	Output is correct
25	Execution timed out	2058 ms	13404 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-