oj.uz

답안 #758258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758258 2023-06-14T10:19:53 Z vjudge1 Hard route (IZhO17_road) C++17
0 / 100
 4 ms 596 KB 
#include <bits/stdc++.h>
#include <array>
#define setall(a, val) for(auto& x : a) x = val
#define all(v) (v.begin()), (v.end())
#define cerr (cerr << "D: ")
#define ll long long
using namespace std;
clock_t start_time;
double get_time() { return (double)(clock() - start_time) / CLOCKS_PER_SEC; }
void init(bool oj = 0) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	srand(time(0)); start_time = clock();
	if (!oj) {
#ifndef ONLINE_JUDGE
		FILE* _ = freopen("in.txt", "r", stdin);
		//FILE* __ = freopen("out.txt", "w", stdout);
#endif
	}
}
const ll HASH_BASE = 31;
const ll MOD = 2000000011;
const ll N = 5e3 + 7;
const ll M = 1e7 + 1e7 / 2;
//####################################################################################

int d[N][N], mx[N], t;
vector<int> path;
vector < vector<int> > v;

void dfs(int x, int p) {
	path.push_back(x);
	if (x == t || t == -1) {
		t = -1;
		return;
	}


	for (int n : v[x]) {
		if (n != p)
			dfs(n, x);
		if (t == -1)
			return;
	}
	path.pop_back();
}

int main() {
	init();

	int n;
	cin >> n;
	v.resize(n);
	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	vector<int> l;
	for (int i = 0; i < n; i++) {
		if (v[i].size() == 1)
			l.push_back(i);

		queue<array<int, 2>>q;
		q.push({ i, 0 });
		while (q.size()) {
			array<int, 2> a = q.front();
			q.pop();
			if (d[i][a[0]])
				continue;
			d[i][a[0]] = a[1];
			mx[i] = max(mx[i], d[i][a[0]]);

			for (int x : v[a[0]]) {
				if (x != i)
					q.push({ x, a[1] + 1 });
			}
		}
	}

	ll ans = 0;
	for (int i = 0; i < l.size(); i++) {
		for (int j = 0; j < l.size(); j++) {
			t = l[j];
			path.clear();
			dfs(l[i], l[i]);
			ll m = 0;
			for (int x : path)
				m = max((ll)mx[x], m);
			ans = max(ans, m * d[l[i]][l[j]]);
		}
	}
	cout << ans << endl;
	cerr << get_time() << "s" << endl;
}

Compilation message

road.cpp: In function 'void init(bool)':
road.cpp:15:9: warning: unused variable '_' [-Wunused-variable]
   15 |   FILE* _ = freopen("in.txt", "r", stdin);
      |         ^
road.cpp: In function 'int main()':
road.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for (int i = 0; i < l.size(); i++) {
      |                  ~~^~~~~~~~~~
road.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for (int j = 0; j < l.size(); j++) {
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -