제출 #887728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887728		beaboss	Hard route (IZhO17_road)	C++14	19 / 100	2058 ms	13404 KiB

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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48